Jocul NIM

Nim

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

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ă.

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ă.

h3. Cerinţă

h2. Cerinta

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

Pentru T configuratii de joc date, sa se determine daca primul jucator are strategie sigura de castig.

h2. Date de intrare

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.

Fişierul de intrare $nim.in$ va contine pe prima linie numarul $T$ de jocuri. Pe urmatoarele $2*T$ linii se vor afla descrierile jocurilor, astfel: pe linia $2*i$ se va afla numarul $N{~i~}$ de gramezi ale jocului $i$, iar pe linia $2*i+1$ se vor afla ${N~i~}$ numere, reprezentand numarul de pietre din fiecare din cele $N{~i~}$ gramezi.

h2. Date de ieşire

Î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.

În fişierul de ieşire $nim.out$ se vor afisa $T$ linii, pe fiecare aflandu-se mesajul $"DA"$, daca jucatorul $1$ are strategie sigura de castig, respectiv $"NU"$, in caz contrar.

h2. Restricţii

* $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^$

* $1 ≤ T ≤ 100$
* $1 ≤ N{~i~} ≤ 10 000$
* Numarul de pietre din oricare gramada este natural pozitiv mai mic sau egal cu $2 000 000 000$.

h2. Exemplu

DA
|

h2. Indicaţii de rezolvare

h2. Indicatii 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âş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$.

Jocul propus in aceasta problema se numeste 'NIM':http://en.wikipedia.org/wiki/Nim. Numim stare castigatoare o configuratie a gramezilor pentru care primul jucator are strategie sigura de castig, respectiv stare necastigatoare o configuratie pentru care primul jucator va pierde. Se observa ca starile castigatoare corespund situatiilor in care suma XOR a numerelor de pietre din gramezi este mai mare ca 0.

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

Pentru a demonstra acest lucru, urmatoarele conditii sunt necesare si 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 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$.

# Dintr-o stare cu suma XOR 0, se poate ajunge doar in stari cu suma XOR pozitiva, sau jocul se termina. Scazand din orice gramada o cantitate poztiva, evident vom schimba configuratia binara a numarului de pietre cu cel putin un bit, deci si suma XOR. Jocul se termina cand toate gramezile au 0 pietre, deci si suma XOR va fi 0.
# Dintr-o stare cu suma XOR pozitiva, se poate ajunge intr-o stare cu suma XOR 0. Cautam o gramada cu un numar X de pietre, care are un bit de 1 pe pozitia bitului cel mai semnificativ al sumei XOR, notata cu S. Din acea gramada se vor scadea X - (X XOR S) pietre, (X XOR S) fiind mai mic decat X deoarece se anuleaza bitul cel mai semnificativ al lui S. Suma XOR ramasa dupa scadere este egala cu 0.

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.

Pentru o demonstratie mai pe larg si alte variante de joc NIM, puteti consulta acest 'articol':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

h2. Aplicaţii

h2. Aplicatii

* 'Xerox':problema/xerox

* 'Joc3':problema/joc3
* 'Nim Game - Give Away!':http://acm.mipt.ru/judge/problems.pl?problem=103

5874