Fişierul intrare/ieşire:copaci.in, copaci.outSursăConcurs Infogim 2018 clasele 6-8
AutorLiana tucarAdăugată deptestPaul Diac ptest
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Copaci

Magdozaur este un monstruleţ cu un rafinat gust estetic. Ea a plantat N copaci (de înălţimi distincte două câte două) aliniaţi frumos într-o linie de la stânga la dreapta spre vale. A venit momentul să-i tundă (pentru a le reda forma perfectă). Deoarece are o macara mai complicată, ea tunde copacii repetând următoarea operaţie: alege copacul de înălţime maximă, şi foloseşte macaraua pentru a tunde acel copac si toţi copacii din drepata lui care n-au fost deja tunşi (fiindcă e uşor sa conducă la vale). Repetă aceasta operaţie până când a tuns toţi copacii.

Magdozaur vă zice înălţimile copacilor de la stânga la dreapta (deal spre vale) şi vă roagă să-i spuneţi câte operaţii trebuie să facă pentru a-şi reface grădina perfetă (a tunde toţi copacii). Deoarece tocmai şi-a luat carnetul de conducere, este darnică şi vă va rasplăti cu 100 de puncte dacă o ajutaţi.

Date de intrare

În fişierul copaci.in se află pe prima linie numărul N reprezentând numărul de copaci. Pe a doua linie se află N numere naturale distincte reprezentând înălţimile copacilor.

Date de ieşire

Afişaţi pe prima linie în fişierul copaci.out numărul de operaţii necesare pentru a tunde toţi copacii.

Restricţii

  • 1 ≤ N ≤ 100.000
  • Înălţimile copacilor sunt numere naturale ≤ 1010

Exemplu

copaci.incopaci.out
11
2 8 1 9 60 57 3 100 5 4 70
5

Explicaţie

Operatia 1:
2 8 1 9 60 57 3 100 5 4 70
Înălţimea 100 este maximă. Tunde toţi copacii din dreapta sa

Operatia 2:
2 8 1 9 60 57 3
Înălţimea 60 este maximă dintre copacii ne-tunşi. Tunde toţi copacii
din dreapta sa

Operatia 3:
2 8 1 9
Înălţimea 9 este maximă dintre copacii ne-tunşi. Tunde toţi copacii
din dreapta sa

Operatia 4:
2 8 1
Înălţimea 8 este maximă dintre copacii ne-tunşi. Tunde toţi copacii

Operatia 5:
2
Înălţimea 2 este maximă dintre copacii ne-tunşi. Tunde toti copacii
din dreapta sa. Acum toţi copacii sunt tunşi.

Trebuie sa te autentifici pentru a trimite solutii. Click aici