Fişierul intrare/ieşire:nim.in, nim.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.3 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

Cerinţă

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

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 ni de grămezi care alcătuiesc jocul i, iar pe linia 2*i+1 se vor afla ni numere, dimensiunile grămezilor.

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.

Restricţii

  • 1 ≤ t ≤ 100
  • 1 ≤ ni ≤ 10 000
  • Numărul de pietre din oricare grămadă este natural pozitiv mai mic sau egal cu 2 * 109

Exemplu

nim.innim.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âş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 şi suficiente:

  1. 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.
  2. 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.

O implementare de 100 de puncte gasiti aici. Pentru o demonstraţie mai pe larg şi alte variante de joc NIM, puteţi consulta acest articol, dar si cel despre teoria jocurilor de pe infoarena.

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content