Diferente pentru summer-challenge-2007/solutii/runda-3 intre reviziile #4 si #5

Nu exista diferente intre titluri.

Diferente intre continut:

Problema este o generalizare a cazului cand K este egal mereu cu 0 (problema pietre de pe infoarena). In cazul cand K este 0 stim ca exista anumite perechi (a, b) de pietre care sunt pierzatoare. Primele perechi de acest gen sunt : (1, 2), (3, 5), (4, 7), (6, 10). Puteti sa verificati ca pentru aceste configuratii initiale primul jucator este pierzator orice ar face. Aceste perechi se pot genera dupa cateva observatii simple:
* diferenta intre termeni creste intodeauna cu 1 (2 - 1 = 1; 3 - 5 = 2; 7 - 4 = 3; 6 - 10 = 4)
* primul numar din fiecare pereche este cel mai mic numar natural strict pozitiv nefolosit inca in perechile anterioare ( (1, 2) -> 3; (1, 2, 3, 5) -> 4; (1, 2, 3, 5, 4, 7) -> 6);
* primul numar din fiecare pereche este cel mai mic numar natural strict pozitiv nefolosit inca in perechile anterioare ( () -> 1; (1, 2) -> 3; (1, 2, 3, 5) -> 4; (1, 2, 3, 5, 4, 7) -> 6);
Pe cazul general unde K poate fi oricat ceea ce se schimba este diferenta intre termeni care creste cu K + 1 in loc de 1 (primul subpunct) (cand K este 0 se verifica);
Tot ce ramane de facut este ca la inceput sa gasim toate perechile (a, b) pierzatoare pentru K-ul dat si sa vedem dupa aceea daca o anumita pereche data in fisierul de intrare se afla sau nu printre cele pierzatoare. Cum A, B <= 100 000 este clar ca pot fi cel mult 100 000 de perechi. Ceea ce ne duce la o complexitate de O(B) precalculare si apoi O(1) pe query (pentru fiecare numar x tinem minte perechea lui y astfel incat (x, y) este pierzator sau 0 in caz ca nu exista acest y);

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.