Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-08-30 09:01:33.
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.

Date de intrare

Fişierul de intrare supermario.in ...

Date de ieşire

În fişierul de ieşire supermario.out ...

Restricţii

  • ... ≤ ... ≤ ...

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?