Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-03-20 19:50:52.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:lumanari.in, lumanari.outSursăAlgoritmiada 2013, Runda 4
AutorAndrei Grigorean, Serban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.2 secLimită de memorie9096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Lumanari

Domnisoarei P. ii plac foarte mult cinele romantice. Ea considera ca o cina este cu atat mai romantica, cu cat sunt aprinse mai multe lumanari la masa la care sta. Proprietarul restaurantului ei favorit stie ca P. ii va trece pragul in urmatoarele seri. Vom numerota aceste seri incepand cu 1. Pentru a o impresiona, el doreste sa aprinda in fiecare seara i exact i lumanari. La sfarsitul serii va stinge lumanarile aprinse. Deasemenea, mai stie ca daca va tine aprinsa o lumanare intr-o seara, inaltimea acesteia va scadea cu 1. El are la dispozitie M lumanari de diferite inaltimi pe care le va folosi numai la masa lui P. Proprietarul vrea sa stie numarul maxim de seri N in care o poate impresiona pe domnisoara P.

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.inlumanari.out
6
1 3 4 5 6 1
5

Explicaţie

Lumanarile vor fi folosite 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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?