Fișierul intrare/ieșire | copaci.in, copaci.out | Sursă | Concurs Infogim 2018 clasele 6-8 |
---|---|---|---|
Autor | Liana Tucar | Adăugată de | Hai la Olimpiada - Iasi Gimnaziu • ptest |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
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.in | copaci.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.