Fişierul intrare/ieşire:	doipatru.in, doipatru.out	Sursă	Lot 2002
Autor	Mugurel Ionut Andreica	Adăugată de
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

DoiPatru

Membrii Lotului National de Informatica sunt foarte mandri de noul joc inventat de ei, pe care l-au denumit asemanator cu o problema de la Olimpiada Internationala de Informatica din anul 2001, care le-a placut foarte mult. Astfel, jocul se numeste DoiPatru.

Pentru acest joc se folosesc N gramezi, fiecare continand cel putin 0 si cel mult 4 bile. Numarul total de bile din toate gramezile este 2N. Doi jucatori muta alternativ. Atunci cand ii vine randul, fiecare jucator este obligat sa efectueze o mutare valida.

O mutare valida consta din alegerea a doua gramezi, dintre care prima gramada are mai multe bile decat cea de a doua. Jucatorul ia o bila din prima gramada si o muta in cealalta. Mutarea se considera valida, doar daca numarul de bile rezultat in a doua gramada dupa mutarea bilei nu este mai mare decat numarul de bile ramas in prima gramada.

Jocul se termina atunci cand nu mai poate fi efectuata nici o mutare valida (daca va ganditi putin, veti constata ca acest lucru se intampla atunci cand fiecare gramada contine doua bile).

Castigatorul jocului este desemnat cel care detine mai multe gramezi la sfarsitul jocului. Bineinteles, daca cei doi jucatori detin un numar egal de gramezi, jocul se considera a fi remiza.

Un jucator detine o gramada daca gramada are doua bile, iar acest numar (de doua bile) a rezultat in urma unei mutari efectuate de jucatorul respectiv. De exemplu, daca un jucator alege o gramada cu 4 bile si una cu o bila, in urma efectuarii mutarii, el va detine cea de-a doua gramada (care va avea doua bile), dar prima nu va apartine deocamdata nici unuia dintre jucatori. Daca alege o gramada cu 3 bile si una cu 0 bile, jucatorul va deveni proprietarul primei gramezi, deoarece, in urma mutarii efectuate, gramada respectiva va ramane cu doua bile. In cazul in care alege o gramada cu 3 bile si una cu o bila, dupa efectuarea mutarii, el va detine ambele gramezi (amandoua au acum doua bile).

Daca un jucator este proprietarul unei gramezi la un moment dat in timpul jocului, nu inseamna ca aceasta gramada va ramane in posesia lui pana la sfarsit. De exemplu, sa presupunem ca jucatorul 1 detine o gramada cu doua bile si este randul jucatorului 2 sa mute. Daca acesta alege o gramada cu 4 bile si gramada cu doua bile ce apartine jucatorului 1, dupa efectuarea mutarii, ambele gramezi vor avea 3 bile, iar numarul de gramezi aflate in posesia jucatorului 1 va scadea cu 1 (gramada detinuta de el anterior nu mai apartine nici unuia din cei doi jucatori, caci nu mai are doua bile).

Daca la inceputul jocului exista unele gramezi avand doua bile, acestea sunt distribuite in mod egal celor doi jucatori. Daca numarul de gramezi cu doua bile este impar, atunci jucatorul 2 va primi cu o gramada mai mult decat jucatorul 1. Jucatorul 1 este cel care efectueaza prima mutare.

Cerinta

Scrieti un program care, pentru un N dat si un set de configuratii initiale ale jocului cu N gramezi, decide rezultatul fiecarei configuratii de joc.

Date de intrare

Pe prima linie a fisierului de intrare doipatru.in se afla doi intregi: N si S, reprezentand numarul de gramezi folosite in joc, respectiv numarul de configuratii initiale ale jocului, descrise in continuare. Pe urmatoarele S linii se afla cate N valori intregi din intervalul [0, 4], a caror suma este egala cu 2N, reprezentand cate o configuratie initiala a jocului.

Date de iesire

In fisierul de iesire doipatru.out, pentru fiecare configuratie initiala a jocului descrisa in fisierul de intrare, in ordinea in care sunt descrise acestea, afisati rezultatul final al jocului, in conditiile in care ambii jucatori joaca optim. Veti afisa valoarea 1, daca jocul este castigat de primul jucator, valoarea 2, daca jocul este castigat de cel de-al doilea sau valoarea 0, daca jocul se termina remiza.

Restrictii si precizari

• 3 ≤ N ≤ 30
• 1 ≤ S ≤ 1000

Exemplu

Cum se trimit solutii?