== include(page="template/taskheader" task_id="nim") ==

Se consideră $n$ grămezi de pietre. Doi jucători vor ridica alternativ oricâte pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră.

Se dau $n$ grămezi, fiecare conţinând un anumit număr de pietre. Doi jucători vor începe să ia alternativ din pietre, astfel: la fiecare pas, jucătorul aflat la mutare trebuie să îndepărteze un număr nenul de pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră.

h3. Cerinţă

Pentru $t$ configuraţii de joc date, să se determine dacă primul jucător are strategie sigură de câştig.

Pentru $t$ configuraţii de joc date, să se determine dacă jucătorul care ia primele pietre are strategie sigură de câştig.

h2. Date de intrare

Fişierul de intrare $nim.in$ va conţine pe prima linie numărul $t$ de jocuri. Pe următoarele $2*t$ linii se vor afla descrierile jocurilor, astfel: pe linia $2*i$ se va afla numărul $n{~i~}$ de grămezi ale jocului $i$, iar pe linia $2*i+1$ se vor afla $n{~i~}$ numere, reprezentând numărul de pietre din grămezi.

Pe prima linie a fişierului de intrare $nim.in$ se va afla numărul $t$ de configuraţii. Pe următoarele $2*t$ linii se vor afla descrierile jocurilor, astfel: pe linia $2*i$ se va afla numărul $n{~i~}$ de grămezi care alcătuiesc jocul $i$, iar pe linia $2*i+1$ se vor afla $n{~i~}$ numere, dimensiunile grămezilor.

h2. Date de ieşire

În fişierul de ieşire $nim.out$ se vor afişa $t$ linii, pe fiecare aflându-se mesajul $"DA"$, dacă jucătorul $1$ are strategie sigură de câştig, respectiv $"NU"$, în caz contrar.

În fişierul de ieşire $nim.out$ se vor afişa $t$ linii, pe linia $i$ aflându-se mesajul $"DA"$, dacă primul jucător are strategie sigură de câştig in jocul $i$, respectiv $"NU"$, în caz contrar.

h2. Restricţii

* $1 ≤ t ≤ 100$.
* $1 ≤ n{~i~} ≤ 10 000$.
* Numarul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu $2 * 10^9^$.

* $1 ≤ t ≤ 100$
* $1 ≤ n{~i~} ≤ 10 000$
* Numărul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu $2 * 10^9^$

h2. Exemplu

h2. Indicaţii de rezolvare

Jocul imparţial propus în această problemă se numeşte 'jocul NIM':http://en.wikipedia.org/wiki/Nim, stând la baza teoriei jocurilor. Numim stare câştigătoare o configuraţie a grămezilor pentru care primul jucător are strategie sigură de câştig, respectiv stare necâştigatoare o configuraţie pentru care primul jucator va pierde. Se observă că stările câştigătoare corespund situaţiilor în care suma XOR a numerelor de pietre din gramezi este mai mare ca 0.

Jocul imparţial propus în această problemă se numeşte 'jocul NIM':http://en.wikipedia.org/wiki/Nim, stând la baza teoriei jocurilor. Numim stare câştigătoare o configuraţie a grămezilor pentru care primul jucător are strategie sigură de câştig, respectiv stare necâştigătoare o configuraţie pentru care primul jucător va pierde. Se observă că stările câştigătoare corespund situaţiilor în care suma $XOR$ a numerelor de pietre din grămezi este mai mare ca $0$.

Pentru a demonstra acest lucru, următoarele condiţii sunt necesare si suficiente:

Pentru a demonstra acest lucru, următoarele condiţii sunt necesare şi suficiente:

# Dintr-o stare cu suma XOR 0, se poate ajunge doar în stări cu suma XOR pozitivă, sau jocul se termină. Scăzând din orice gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel puţin un bit, deci şi suma XOR. Jocul se termină cand toate grămezile au 0 pietre, deci şi suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitivă, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o grămadă cu un număr X de pietre, care are un bit de 1 pe poziţia bitului cel mai semnificativ al sumei XOR, notată cu S. Din acea grămadă se vor scădea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anulează bitul cel mai semnificativ al lui S. Suma XOR rămasă după scădere este egală cu 0.

# Dintr-o stare cu suma $XOR 0$, se poate ajunge doar în stări cu suma $XOR$ pozitivă, sau jocul se termină. Scăzând din orice grămadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel puţin un bit, deci şi suma $XOR$. Jocul se termină când toate grămezile au $0$ pietre, deci şi suma $XOR$ este $0$.
# Dintr-o stare cu suma $XOR$ nenulă, se poate ajunge într-o stare cu suma $XOR 0$. Căutăm o grămadă cu un număr $X$ de pietre, care are, în reprezentarea sa binară, valoarea $1$ pe poziţia bitului cel mai semnificativ al sumei $XOR$, să o notăm cu $S$. Din acea grămadă se vor scădea $X - (X XOR S)$ pietre, $(X XOR S)$ fiind mai mic decât $X$ deoarece se anulează bitul cel mai semnificativ al lui $S$. Suma $XOR$ rămasă după scădere este egală cu $0$.

Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

O implementare de $100$ de puncte gasiti 'aici':job_detail/608541?action=view-source. Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf, dar si cel despre 'teoria jocurilor':numerele-sprague-grundy de pe infoarena.

h2. Aplicaţii

5874