| Fișierul intrare/ieșire | lalele.in, lalele.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Lalele (clasele 9-10)
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?
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.
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ă.
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.
Exemplu
| lalele.in | lalele.out |
|---|---|
| 11 3 6 2 9 2 0 3 5 1 0 |
10 11 8 |
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).
