Fişierul intrare/ieşire:lalele.in, lalele.outSursăad-hoc
AutorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inlalele.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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici