== include(page="template/taskheader" task_id="stiva") ==
Poveste si cerinta...
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 când 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)$, $top4$, $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$.
h2. Cerinta
Dat fiind un sir format din litere mari, sa se determine numarul minim de operatii dintr-o secventa corecte care afiseaza sirul dat.
h2. Date de intrare
Fisierul de intrare $stiva.in$ ...
Fisierul de intrare $stiva.in$ contine pe prima linie un sir format numai din litere mari.
h2. Date de iesire
In fisierul de iesire $stiva.out$ ...
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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* Lungimea sirului este ≤ $500$ .
h2. Exemplu
table(example). |_. stiva.in |_. stiva.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| ABCACBA
| 15
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="stiva") ==
