Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | lumanari.in, lumanari.out | Sursă | Algoritmiada 2013, Runda 4 |
| Autor | Andrei Grigorean, Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 9096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lumanari
In camera magica toata lumina trebuie sa provina de la lumanari. Vrem sa luminam camera timp de N zile, numerotate convenabil de la 1 la N. Stim ca in ziua i trebuie sa aprindem i lumanari pentru a lumina camera. La sfarsitul zilei vom stinge lumanarile aprinse. Stim ca daca tinem o lumanare aprinsa timp de o zi, inaltimea acesteia va scadea cu 1. Calculati valoarea maxima pe care o poate lua N.
Date de intrare
Fişierul de intrare lumanari.in va contine pe prima linie numarul M cu semnificatia din enunt. Pe a doua linie a fisierului de intrare se vor gasi M numere naturale reprezentand inaltimile celor M lumanari.
Date de ieşire
În fişierul de ieşire lumanari.out se va afla valoarea maxima a lui N.
Restricţii
- 1 ≤ M ≤ 200 000
- Inaltimile lumanarilor vor fi numere naturale mai mici ca 109
- Daca o lamanare ajunge la inaltimea 0, nu mai poate fi folosita.
Exemplu
| lumanari.in | lumanari.out |
|---|---|
| 6 1 3 4 5 6 1 | 5 |
Explicaţie
Vom arde lumanarile in urmatorul mod in cele 5 zile:
Ziua 0: 1 3 4 5 6 1
Ziua 1: 0 3 4 5 6 1
Ziua 2: 0 2 3 5 6 1
Ziua 3: 0 2 2 4 5 1
Ziua 4: 0 1 1 3 4 1
Ziua 5: 0 0 0 2 3 0
