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ă.
Cerinta
Pentru T configuratii de joc date, sa se determine daca primul jucator are strategie sigura de castig.
Date de intrare
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 Ni 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 Ni gramezi.
Date de ieşire
Î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.
Restricţii
- 1 ≤ T ≤ 100
- 1 ≤ Ni ≤ 10 000
- Numarul de pietre din oricare gramada este natural pozitiv mai mic sau egal cu 2 000 000 000.
Exemplu
| nim.in | nim.out |
|---|---|
| 2 4 1 3 5 7 3 4 8 17 | NU DA |
Indicatii de rezolvare
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, urmatoarele conditii sunt necesare si suficiente:
- 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.
