Fişierul intrare/ieşire:stiva.in, stiva.outSursăONI 2008 - baraj
AutorEmanuela CerchezAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.2 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stiva

Sa consideram o stiva, initial vida. Putem efectua urmatoarele operatii:

  • push(X) - se introduce in stiva litera X (evident, in varful stivei);
  • pop - se extrage litera aflata la varful stivei (operatia pop se executa atunci cand stiva este nevida);
  • top - se afiseaza litera aflata la varful stivei (operatia top se executa atunci cand stiva este nevida).

O secventa de operatii este considerata corecta daca:

  • initial stiva este vida;
  • se executa o serie de operatii push, pop, top, fara a executa pop sau top cand stiva este vida;
  • la final stiva este vida.

Utilizand secvente corecte de operatii, putem afisa diferite siruri de caractere.
De exemplu, sirul ABDADBA poate fi generat astfel: push(A), top, pop, push(B), top, pop, push(D), top, pop, etc.
O alta secventa de operatii corecta, dar mai scurta ar fi: push(A), top, push(B), top, push(D), top, push(A), top, pop, top, pop, top, pop, top, pop.

Cerinta

Dat fiind un sir format din litere mari, sa se determine numarul minim de operatii dintr-o secventa corecta care afiseaza sirul dat.

Date de intrare

Fisierul de intrare stiva.in contine pe prima linie un sir format numai din litere mari.

Date de iesire

Fisierul de iesire stiva.out va contine o singura linie pe care va fi scris numarul minim de operatii dintr-o secventa corecte care afiseaza sirul din fisierul de intrare.

Restrictii

  • Lungimea sirului este ≤ 500 .

Exemplu

stiva.instiva.out
ABCACBA
15
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content