==Include(page="template/taskheader" task_id="joc3")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Joc3
 
 
 
Gigel si Andrei au N saci cu pietre pretioase numerotati de la 1 la N. Pentru ca nu vor sa imparta pietrele intre ei, au hotarat sa joace un joc iar castigatorul sa ia toate pietrele. Jocul consta in efectuarea alternativa a unor mutari. O mutare consta in selectarea unor pietre dintr-un sac i (1 <= i < N) si mutarea acestora in sacul i + 1. Jucatorul care nu mai poate efectua nici o mutare (atunci cand toate pietrele sunt asezate in ultimul sac) pierde jocul.
 
h2. Cerinta
 
Stiind atat numarul de saci si configuratia acestora, cat si faptul ca Gigel va efectua prima mutare determinati, daca exista, o strategie de castig pentru el.
 
h2. Date de Intrare
 
Pe prima linie a fisierului joc3.in se va afla N, numarul de saci. Urmeaza N linii, pe linia i aflandu-se numarul de pietre pretioase din sacul i.
 
h2. Date de Iesire
 
In cazul in care Gigel nu are strategie de castig fisierul de iesire joc3.out va contine pe prima linie valoarea -1. Altfel, afisati pe prima linie numerele p si q ce codifica mutarea initiala pe care ar trebui sa o efectueze Gigel pentru a castiga jocul (p este numarul sacului, iar q numarul de pietre). In cazul in care exista mai multe mutari initiale ce ar putea duce la castigarea sigura a jocului, afisati mutarea care are p minim. Daca totusi mai sunt cazuri de egalitate, afisati mutarea cu q minim.
 
h2. Restrictii si precizari:
 
o 1 <= N <= 100000
 
o 0 <= numarul de pietre dintr-un sac <= 10000
 
h2. Exemplu:
 
joc3.in joc3.out Explicatii
5 2 2 Efectuand aceasta mutare Gigel va castiga daca va continua sa joace perfect. Nu exista alta mutare cu p sau q mai mic.
 
2
 
5
 
4
 
3
 
1
5 -1 Cum toate pietrele sunt asezate in ultimul sac, Gigel nu poate efectua vreo mutare.
 
0
 
0
 
0
 
0
 
10000
 

==Include(page="template/taskheader" task_id="joc3")==
 
Gigel si Andrei au $N$ saci cu pietre pretioase numerotati de la $1$ la $N$. Pentru ca nu vor sa imparta pietrele intre ei, au hotarat sa joace un joc iar castigatorul sa ia toate pietrele. Jocul consta in efectuarea alternativa a unor mutari. O mutare consta in selectarea unor pietre dintr-un sac $i$ ({$1$} ≤ $i$ < $N$) si mutarea acestora in sacul $i+1$. Jucatorul care nu mai poate efectua nici o mutare (atunci cand toate pietrele sunt asezate in ultimul sac) pierde jocul.
 
h2. Cerinta
 
Stiind atat numarul de saci si configuratia acestora, cat si faptul ca Gigel va efectua prima mutare determinati, daca exista, o strategie de castig pentru el.
 
h2. Date de intrare
 
Pe prima linie a fisierului $joc3.in$ se va afla $N$, numarul de saci. Urmeaza $N$ linii, pe linia $i$ aflandu-se numarul de pietre pretioase din sacul $i$.
 
h2. Date de iesire
 
In cazul in care Gigel nu are strategie de castig fisierul de iesire $joc3.out$ va contine pe prima linie valoarea $-1$. Altfel, afisati pe prima linie numerele $p$ si $q$ ce codifica mutarea initiala pe care ar trebui sa o efectueze Gigel pentru a castiga jocul ({$p$} este numarul sacului, iar $q$ numarul de pietre). In cazul in care exista mai multe mutari initiale ce ar putea duce la castigarea sigura a jocului, afisati mutarea care are $p$ minim. Daca totusi mai sunt cazuri de egalitate, afisati mutarea cu $q$ minim.
 
h2. Restrictii si precizari
 
* $1$ ≤ $N$ ≤ $100.000$
* $0$ ≤ numarul de pietre dintr-un sac ≤ $10.000$
 
h2. Exemple
 
table(example). |_. joc3.in |_. joc3.out |
| 5
2
5
4
3
1 | 2 2 |
 
h3. Explicatie
 
Efectuand aceasta mutare Gigel va castiga daca va continua sa joace perfect. Nu exista alta mutare cu $p$ sau $q$ mai mic.
 
table(example). |_. joc3.in |_. joc3.out |
| 5
0
0
0
0
10000 | -1 |
 
h3. Explicatie
 
Cum toate pietrele sunt asezate in ultimul sac, Gigel nu poate efectua vreo mutare.
 
==Include(page="template/taskfooter" task_id="joc3")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/joc3/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="joc3")==

1318