Doi prieteni au inventat un nou joc – « jocul pietricelelor ». Ei au la dispoziţie N grămezi, fiecare dintre ele conţinând un număr de pietricele.
Jocul constă în alegerea unui număr oarecare de grămezi din cele N date, pentru a obţine în total (adunând numărul de pietricele din grămezile selectate) un număr de pietricele cu 1 mai mare decât ultimul număr obţinut de partenerul de joc. Primul jucător trebuie să obţină la prima sa mutare un total de 1 pietricică. Deci, obligatoriu al doilea jucător trebuie să obţină la prima sa mutare un total de 2 pietricele. La a doua mutare, primul jucator este obligat sa obţină un total de 3 pietricele, ş.a.m.d.
Câştigă cel care a obţinut totalul maxim, sau, altfel spus, pierde cel care nu reuşeşte să obţină la rândul său un total cu exact o pietricică mai mare decât ultimul total obţinut de partenerul de joc.
Cerinţă
Scrieţi un program care determină numărul de pietricele obţinut la ultima sa mutare de jucătorul câştigător.
Date de intrare
Fişierul de intrare pietre.in conţine:
– pe prima linie numărul N de grămezi;
– pe a doua linie N numere ordonate crescător, reprezentând numărul de pietricele din fiecare grămadă.
Date de ieşire
Fişierul de ieşire pietre.out va conţine pe prima linie numărul determinat. Dacă jocul nu poate începe, fiindcă lipseşte grămada care conţine o pietricică, în fişier se va afişa valoarea 0.
Restricţii
1<=N<=60000
Numărul de pietricele dintr-o grămadă <=60000
Deoarece adunarea numărului de pietricele din grămezile selectate durează, cei doi prieteni au hotărât să joace până se obţine maxim valoarea 60000 (dacă este posibil). În cazul în care se pot obţine toate valorile de la 1 la 60000 se va afişa valoarea 60001
Grămezile selectate de un jucător rămân pe loc, nu se colectează.
Exemple
pietre.in
pietre.out
Explicaţii
7
1 2 4 9 10 11 12
7
Notam PJ primul jucător şi DJ al doilea jucător. PJ are la dispoziţie o grămadă cu o pietricică: 1
DJ are la dispoziţie o grămadă ce conţine două pietricele: 2
PJ alege primele două grămezi: 1+2=3
DJ are la dispoziţie o grămadă ce conţine 4 pietricele: 4)
PJ alege prima şi a trei grămadă: 1+4=5
DJ alege a doua şi a treia grămadă: 2+4=6
PJ alege primele trei grămezi: 1+2+4=7
Jocul ia sfârşit deoarece al doilea jucător nu poate obţine o grămadă ce conţine 8 pietricele.