Diferențe pentru problema/lalele între reviziile #11 si #6

Lalele (clasele 9-10)

lalele

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$ 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 zero înseamnă că următoarele $d$ zile sunt zile de târg.

h2. Date de ieșire

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$.

* $1 ≤ N ≤ 1.000.000$

* 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.

table(example).
|_. lalele.in |_. lalele.out |

| 11
3 6
2 9
2 0
3 5
1 0
| 10

| 9
3 8 7 0 2 10 9 0 0
| 8
10

11

8

|
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).

În prima zi de târg Ion are 3 lalele de înălțimi 6, 10 și 8 (de exemplu, laleaua sădită la înălțime 3 a crescut 3 zile până la înălțimea 6). Ion taie două dintre lalele (10 și 8), din care cea mai mică este 8. El păstrează laleaua 6.
În a doua zi de târg, Ion are 4 lalele de înălțimi 10, 10, 5 12 (de exemplu, laleaua rămasă după primul târg a crescut cu încă 4 cm, până la 10). Ion taie lalelele 10 și 12, din care cea mai mică este 10. El păstrează lalelele 5 și 10.
 
În ultima zi de târg, cele două lalele rămase din ziua anterioară au crescut la 11, respectiv 6 cm. Ion taie laleaua 11 și o păstrează pe 6.

== include(page="template/taskfooter" task_id="lalele") ==