h2. 'Alinuta':problema/alinuta

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; (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 STIU SA DEMONSTREZ LUCRURILE DE MAI SUS (se observa cu un back in timpul concursului :P) (rog pe cineva mai competent sa gaseasca o demonstratie))
 
Cateva observatii pentru demonstratie:

Problema este o generalizare a cazului cand $K$ este egal mereu cu $0$ (problema 'pietre':problema/pietre). 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$; $(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 precalculam 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$).
 
In general pentru problemele de acest tip in timpul concursului se observa regula cu ajutorul unui back.
 
*Rog pe cineva sa scrie si o demonstratie a acestui algoritm*
Cateva observatii care sunt importante pentru demonstratie:
 
* $(a, b)$ si $(b, a)$ sunt echivalente
* daca $(a, b)$ este configuratie pierzatoare atunci orice $(a, c)$ cu $c > b$ este configuratie castigatoare; de aici rezulta ca pentru un a fixat avem un singur $b$ pentru care $(a, b)$ e pierzatoare restul configuratiilor fiind castigatoare

h2. 'Dame 2':problema/dame2
Problema se rezolva prin metoda backtracking. Se iau toate posibilitatile de a aseza damele pe tabla de sah astfel incat oricare doua dame sa nu se atace. Ca sa intre in timp trebuiesc facute unele optimizari cum ar fi:

* atunci cand punem o dama marcam linia, coloana, prima diagonala si a doua dioagonala pe care este dama ca fiind ocupate pentru ca mai tarziu sa stim ca pe acestea nu putem pune alta dama (optimizam verificarea pentru a vedea daca putem sa punem o dama pe o anumita pozitie sau nu)
* tinem minte numarul minim de dame necesar gasit pana acum si in backtracking daca cumva trecem de acel numar cand cautam o solutie nu mai continuam pentru ca nu are sens (sigur am gasit o solutie cu numar de dame mai mic inainte) (initial acest numar este infinit)

* dupa ce am gasit o solutie cu un anumit numar de dame verificam daca fiecare patratel este atacat de o dama in O(1) folosindu-ne de informatiile stiute de la primul subpunct, si anume: un patratel (x, y) este atacat de o dama daca cel putin una din linia, coloana, prima diagonala, a doua diagonala sunt marcate ca fiind o dama pe ele.

* dupa ce am gasit o solutie cu un anumit numar de dame verificam daca fiecare patratel este atacat de o dama in $O(1)$ folosindu-ne de informatiile stiute de la primul subpunct, si anume: un patratel $(x, y)$ este atacat de o dama daca cel putin una din linia, coloana, prima diagonala, a doua diagonala sunt marcate ca fiind o dama pe ele.