Fişierul intrare/ieşire:balanta.in, balanta.outSursăad-hoc
AutorDin FolclorAdăugată deb0rk4nGramatovici Paul b0rk4n
Timp execuţie pe test1 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Balanta

Ca oricarui copil, lui Anatop ii plac foarte mult dulciurile. Bunica lui i-a promis ca in urmatoarele N zile ii va da cate A i (1≤i≤n) cutii cu bomboane. In fiecare zi, de dimineata, inainte sa plece la scoala, Anatop mananca jumatate de cutie. Cand se intoarce seara acasa, Anatop, vrea sa termine cutia inceputa de dimineata, insa nu mai stie care este aceasta. Pentru a gasi cutia inceputa el foloseste o veche balanta cu talere. La o cantarire el poate sa puna oricate cutii de bomboane pe fiecare dintre talere. Astfel balanta poate sa se incline spre talerul mai greu sau sa ramana in echilibru cand cantitatile de bomboane sunt egale pe ambele talere. Ajutati-l pe Anatop sa determine numarul minim de cantariri pe care Anatop trebuie sa le faca in fiecare zi pentru a fi sigur ca afla care este cutia inceputa.

Date de intrare

Fişierul de intrare balanta.in va contine pe prima linie numarul N de zile. Pe urmatoarele N linii se va afla cate un numar A i (1≤i≤n) care reprezinta numarul de cutii primite in ziua i.

Date de ieşire

În fişierul de ieşire balanta.out va avea N linii. Pe fiecare linie i (1≤i≤n) va fi scris cate un numar reprezentand numarul minim de catariri pe care Anatop trebuie sa le faca pentru a fi sigur ca afla care este cutia inceputa in ziua i.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ A i ≤ 1.000.000.000

Exemplu

balanta.inbalanta.out
5
1
3
5
15
34
1
1
2
3
4

Explicaţie

Pentru 15 cutii sunt necesare 3 cantariri. In prima cantarire se vor pune 7 cutii pe fiecare taler, in a doua se vor pune 3 cutii pe fiecare taler, iar in a treia se va pune o cutie pe fiecare taler.

Trebuie sa te autentifici pentru a trimite solutii. Click aici