== include(page="template/taskheader" task_id="lalele") ==
După ce s-a pensionat, Ion s-a apucat să cultive lalele. Inițial, grădina lui este goală. În zilele obișnuite, Ion sădește o lalea de o înălțime oarecare. Toate lalelele sădite cresc cu 1 cm pe zi. În unele zile speciale, Ion participă la târguri de flori. În acele zile, el nu sădește nimic, ci taie jumătate dintre lalele (rotunjit în sus). Ion taie mereu cele mai înalte lalele și pleacă să le vândă.
În fiecare zi de târg, Ion se întreabă: care este înălțimea celei mai mici lalele pe care o taie?
Poveste și cerință...
h2. Date de intrare
Fișierul de intrare $lalele.in$ conține pe prima linie numărul de zile $N$ în care Ion grădinărește. Pe următoarele linii se află perechi de numere întregi, $d x$. Când $x$ este un număr întreg pozitiv înseamnă că Ion sădește, timp de $d$ zile consecutive, câte o lalea de $x$ cm înălțime. Când $x$ este 0 înseamnă că următoarele $d$ zile sunt zile de târg.
Fișierul de intrare $lalele.in$ ...
h2. Date de ieșire
În fișierul de ieșire $lalele.out$ se va scrie, pentru fiecare zi de târg, o linie conținând un singur număr, reprezentând valoarea celei mai mici lalele pe care Ion o taie pentru ziua de târg respectivă.
În fișierul de ieșire $lalele.out$ ...
h2. Restricții
* $1 ≤ N ≤ 5.000.000$
** (Ion trăiește până la o vârstă respectabilă, datorită unei diete bazate tot pe lalele.)
* $d > 0$ pentru toate perechile $d x$.
* Suma valorilor $d$ din fișier este egală cu [$N$].
* La sădire, lalelele au între 1 și 1.000.000.000 cm.
* Se garantează că Ion are întotdeauna lalele de tăiat în zilele de târg.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. lalele.in |_. lalele.out |
| 11
3 6
2 9
2 0
3 5
1 0
| 10
11
8
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
* ziua 1: Ion nu are lalele. Plantează una de înălțime 6.
* ziua 2: Ion are o lalea de înălțime 7. Plantează una de înălțime 6.
* ziua 3: Ion are lalele de înălțimi (7, 8). Plantează una de înălțime 6.
* ziua 4: Ion are lalele de înălțimi (7, 8, 9). Plantează una de înălțime 9.
* ziua 5: Ion are lalele de înălțimi (8, 9, 10, 10). Plantează una de înălțime 9.
* ziua 6 (târg): Ion are lalele de înălțimi (9, 10, 10, 11, 11). Le taie pe (10, 11, 11).
* ziua 7 (târg): Ion are lalele de înălțimi (10, 11). O taie pe 11.
* ziua 8: Ion are o lalea de înălțime 11. Plantează una de înălțime 5.
* ziua 9: Ion are lalele de înălțimi (6, 12). Plantează una de înălțime 5.
* ziua 10: Ion are lalele de înălțimi (6, 7, 13). Plantează una de înălțime 5.
* ziua 11 (târg): Ion are lalele de înălțimi (6, 7, 8, 14). Le taie pe (8, 14).
...
== include(page="template/taskfooter" task_id="lalele") ==
