Fişierul intrare/ieşire:g.in, g.outSursăHappy Coding 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.75 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

G

Doi jucatori (numerotati 1 si 2) joaca urmatorul joc: Ei au la dispozitie N gramezi, numerotate de la 1 la N. Gramada i contine gpi pietre. Cei doi jucatori efectueaza mutari alternativ, prima mutare fiind efectuata de jucatorul 1. O mutare consta in alegerea unei gramezi (avand G>0 pietre) si efectuarea uneia din urmatoarele actiuni:

  • daca G≥1, jucatorul poate lua o piatra din gramada.
  • daca G≥2, jucatorul poate imparti gramada in doua gramezi continand G1, respectiv G2 pietre, astfel incat G1+G2=G, G1>0 si G2>0.
  • daca G≥3, jucatorul poate lua o piatra din gramada, iar restul gramezii il poate imparti in doua gramezi continand G1, respectiv G2 pietre, astfel incat G1+G2=G-1, G1>0 si G2>0.

Jocul se termina cand nu se mai poate efectua nicio mutare (toate gramezile sunt goale), iar jucatorul care a efectuat ultima mutare este castigatorul. Scrieti un program care determina care dintre cei doi jucatori are strategie sigura de castig.

Date de intrare

Prima linie a fisierului de intrare g.in contine numarul natural T, reprezentand numarul de teste descrise in fisier. Un test consta din doua linii: pe prima linie se afla numarul initial de gramezi N, iar pe a doua linie se afla numerele gp1, ..., gpN, separate prin cate un spatiu.

Date de iesire

In fisierul de iesire g.out veti afisa T linii, cate una pentru fiecare test, in ordinea in care apar testele in fisierul de intrare. Pe fiecare linie se va gasi numarul 1, daca jucatorul 1 are strategie sigura de castig, respectiv 2, daca cel de-al doilea jucator are strategie sigura de castig.

Restrictii

  • 1 ≤ T ≤ 16
  • 1 ≤ N ≤ 100.000
  • Numarul de pietre dintr-o gramada este un numar intreg din intervalul [1, 2.100.000.000].

Exemplu

g.ing.out
5
1
1
1
2
1
3
3
1 2 3
4
1 3 2 4
1
1
1
1
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?