Fişierul intrare/ieşire:supermario.in, supermario.outSursăInfoarena Monthly 2014, Runda 8
AutorAndrei Heidelbacher, Teodor PlopAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insupermario.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content