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