NézetNyomtat

Pecsételő
Címkék > Feladat

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