Pecsételő
Egy halom dolgozatot kell értékelnünk az amerikai rendszer szerint, ahol
"A" a legjobb "jegy". A dolgozatok elég jók, a legrosszabb is "C". Az értékelést egy speciális pecséttel jelezzük: van tetszőlegesen sok A, B és C sablonunk, és ha egy A-val pecsételtünk, majd egy B-t kellene, akkor nem cserélünk sablont, hanem az A elé helyezzük a B-t. Tehát a pecsét úgy működik mint egy verem. A következő műveletek megengedettek:
- PUSH X: felhelyezi az "X" sablont
- PRINT: pecsétel a legfelső sablonnal
- POP: leveszi a legfelső sablont (és így az alatta lévő lesz a legfelső)
Feladat
Ismerve a dolgozatok érdemjegyeinek sorozatát (ami A,B és C karakterekből álló karakterlánc), számoljuk ki, hogy legkevesebb hány "veremművelet" kell az összes jegy lepecsételéséhez, ha legvégül még a pecsételő eszközt is "le kell üríteni".
Bemenet
Az első sor a tesztesetek számát adja meg, majd a karakterláncok következnek.
Kis teszteknél legfeljebb 100, nagyoknál legfeljebb 7000 karakterből áll egy eset, a tesztesetek száma legfeljebb 100.
Kimenet
A kimenet minden sora a megfelelő karakterlánchoz tartozó minimális műveleti számot tartalmazza.
Példa
|
Művelet
|
Eddig kinyomtatva
|
Verem
|
0. -
1. Push A
2. Print
3. Push B
4. Print
5. Push C
6. Print
7. Print
8. Pop
9. Print
10. Pop
11. Print
12. Pop
|
-
-
A
A
AB
AB
ABC
ABCC
ABCC
ABCCB
ABCCB
ABCCBA
ABCCBA
|
-
A
A
AB
AB
ABC
ABC
ABC
AB
AB
A
A
-
|
Tesztadatok
