Revizia anterioară Revizia următoare
| 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 câte o lalea în fiecare zi, cu o înălțime de x cm (x variază de la o lalea la alta). Toate lalelele cresc cu 1 cm pe zi. În unele zile speciale, Ion participă la târguri de flori. În acele zile, el 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 zero î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 ≤ 500.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.
Exemplu
| lalele.in | lalele.out |
|---|---|
| 9 3 8 7 0 2 10 9 0 0 |
8 10 11 |
Explicație
Î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.
