| Fişierul intrare/ieşire: | supermario.in, supermario.out | Sursă | Infoarena Monthly 2014, Runda 8 |
| Autor | Andrei Heidelbacher, Teodor Plop | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Super Mario
Lupta cu ţestoasele este o treabă grea chiar şi pentru Super Mario, eroul acestei probleme. Ce ar fi să îi oferim o mână de ajutor?
Super Mario are de înfruntat armata teribilă a ţestoaselor Koopa Troopas. Armata este formată din N ţestoase numerotate de la 1 la N, dispuse de la stânga la dreapta pe axa Ox a jocului nostru 2D (ţestoasa cu numărul de ordine 1 este cea mai din stânga, iar ţestoasa cu numărul de ordine N este cea mai din dreapta).
Misiunea lui Super Mario este să distrugă toate cele N ţestoase de pe platformă. Super Mario poate sări pe o ţestoasă la alegere din cele N. De frică, ţestoasa se va ascunde în carapace, iar Super Mario va putea să o folosească ca o armă pentru a distruge celelalte ţestoase.
Fiecare ţestoasă i are o putere egală cu P[i]. Dacă Super Mario sare pe ţestoasa i şi alege să o împingă către dreapta, această ţestosă va distruge toate ţestoasele aflate în dreapta ei, până la prima ţestoasă care are o putere strict mai mare decât ţestoasa i. Analog, dacă Super Mario sare pe ţestoasa i şi alege să o împingă în stânga, aceasta va distruge toate ţestoasele aflate în stânga ei, până la prima ţestoasă care are o putere strict mai mare decât ţestoasa i.
Altfel spus:
- Super Mario sare pe ţestoasa i şi o împinge către dreapta. Fie k (i < k) cel mai mic număr cu proprietatea că P[i] < P[k]. Toate ţestoasele j (i < j < k) vor fi distruse, inclusiv ţestoasa i. Dacă nu există un k în şir cu această proprietate, ţestoasa va distruge toate ţestoasele din dreapta ei, inclusiv pe ea însăşi.
- Super Mario sare pe ţestoasa i şi o împinge către stânga. Fie k (k < i) cel mai mare număr cu proprietatea că P[i] < P[k]. Toate ţestoasele j (k < j < i) vor fi distruse, inclusiv ţestoasa i. Dacă nu există un k în şir cu această proprietate, ţestoasa va distruge toate ţestoasele din stânga ei, inclusiv pe ea însăşi.
Se dau N şi un şir de numere naturale P[i]. Să se afişeze numărul minim de ţestoase pe care Super Mario trebuie să sară şi să le împingă, în orice direcţie doreşte el, pentru a distruge toate cele N ţestoase.
Date de intrare
Fişierul de intrare supermario.in conţine pe prima linie numărul natural N. Pe cea de-a doua linie se găsesc N numere naturale P[i], având semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire supermario.out se va găsi un singur număr natural, reprezentând numărul minim de ţestoase pe care trebuie să sară Super Mario pentru a le distruge pe toate.
Restricţii
- 1 ≤ N ≤ 105
- 1 ≤ P[i] ≤ 109
- Se garantează că puterile ţestoaselor sunt distincte două cate două.
Exemplu
| supermario.in | supermario.out |
|---|---|
| 13 1 2 4 3 15 14 13 12 11 10 9 8 7 | 2 |
| 1 123456 | 1 |
Explicaţie
Pentru primul exemplu:
Şirul iniţial al ţestoaselor:
1 2 4 3 15 14 13 12 11 10 9 8 7
Super Mario va sări pe ţestoasa cu puterea 14 şi o va împinge către dreapta. Astfel, şirul ţestoaselor devine:
1 2 4 3 15
Acum, Super Mario va sări pe ţestoasa cu puterea 15 şi o va împinge către stânga. Toate ţestoasele vor fi distruse.
Pentru cel de-al doilea exemplu:
Super Mario va sări pe singura ţestoasă din şir şi o va împinge fie în dreapta, fie în stânga.
