Szczegółowe omówienie zadania Loteria.
Zadanie powstało na podstawie problemu jaki otrzymują osoby które chcą pracować w firmie Google.
Link do powyższego omówienia zadania Loteria:
https://youtu.be/xF5wlR-xX8g?t=4631
Link do zadania Loteria:
https://szkopul.edu.pl/problemset/problem/loteriazad/site
Zadanie Loteria wymaga użycia algorytmu Binary Search.
Znalezienie dwóch liczb które sumują się do zadanej wartości – to jeden z problemów jaki otrzymują kandydaci do Google podczas interview.
Trudny?
Oczywiście nie.
Też może być tym który wymyśla jak ma działać komputer, Facebook czy… nowy start-up!
Oczywiście nie.
Też może być tym który wymyśla jak ma działać komputer, Facebook czy… nowy start-up!
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
https://youtu.be/QgLyXYmFQeU?t=2019
——-
Kod C++ programu Loteria, który jest omówiony w powyższym filmie i który otrzymuje 100%
Kod C++ programu Loteria, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAX_LOSOW = 10000010;
int losy[MAX_LOSOW];
int BinarySearchPierwszy (int poczatek, int koniec, int wartosc) {
int srodek;
while (poczatek < koniec) {
srodek = (poczatek + koniec) / 2;
if (losy[srodek] >= wartosc)
koniec = srodek;
else
poczatek = srodek + 1;
}
if ( losy[poczatek] == wartosc )
return poczatek;
return -1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, liczba_losow;
int p1_index, p2_index, p2_wartosc, i;
cin >> k;
cin >> liczba_losow;
for (i=1; i<=liczba_losow; ++i)
cin >> losy[i];
sort (losy+1, losy+liczba_losow+1);
for (p1_index=1; p1_index<liczba_losow; ++p1_index) {
p2_wartosc = k - losy[p1_index];
p2_index = BinarySearchPierwszy (p1_index+1, liczba_losow, p2_wartosc);
if (p2_index == -1)
continue;
cout << "Mozesz ryzykowac\n";
return 0;
}
cout << "Bez szans\n";
return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Loteria - tym samym który został użyty w omówieniu