| Fişierul intrare/ieşire: | balanta.in, balanta.out | Sursă | ad-hoc |
| Autor | Din Folclor | Adăugată de |  Gramatovici Paul •b0rk4n |
| Timp execuţie pe test | 1 sec | Limită de memorie | 1024 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
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.in | balanta.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.
