Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nim.in, nim.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Jocul 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ă.
Cerinţă
Pentru t configuraţii de joc date, să se determine dacă primul jucător are strategie sigură de câştig.
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 ni de grămezi ale jocului i, iar pe linia 2*i+1 se vor afla ni numere, reprezentând numărul de pietre din grămezi.
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.
Restricţii
- 1 ≤ t ≤ 100.
- 1 ≤ ni ≤ 10 000.
- Numarul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu 2 * 109.
Exemplu
| nim.in | nim.out |
|---|---|
| 2 4 1 3 5 7 3 4 8 17 | NU DA |
Indicaţii de rezolvare
Jocul imparţial propus în această problemă se numeşte jocul 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.
Pentru a demonstra acest lucru, următoarele condiţii 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 gramadă o cantitate pozitivă, evident vom schimba configuraţia binară a numărului de pietre cu cel putin un bit, deci şi suma XOR. Jocul se termină cand toate gramezile au 0 pietre, deci şi suma XOR va fi 0.
- Dintr-o stare cu suma XOR pozitiva, se poate ajunge intr-o stare cu suma XOR 0. Căutăm o gramadă 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.
Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest articol
