Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-08-30 09:12:35.
Revizia anterioară   Revizia următoare  

 

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.
  • 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.

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
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?