Programozás‎ > ‎Feladatok‎ > ‎

ABC Ládapakolás

Egy vállalat udvarán egyetlen sorban vannak az elszállításra várakozó üres ládák. Három különböző típusú láda van, jelölje ezeket A, B és C. Minden láda egyik oldalán nyitott kocka alakú. Az A-típusú láda a legnagyobb és a C-típusú a legkisebb. Tehát minden C-típusú láda belerakható A-típusú és B-típusú ládába, minden B-típusú belerakható A-típusúba és A-típusúba belerakható B-típusú, majd ebbe egy C-típusú. Az a cél, hogy a ládákat úgy pakoljuk össze, hogy a lehető legkevesebb összepakolt láda legyen. A pakolást olyan robot végzi, amely a ládasor felett tud mozogni mindkét irányban, de ládát csak balról jobbra mozogva tud szállítani.

Feladat

Készíts programot, amely megadja, hogy legkevesebb hány ládába lehet összepakolni a ládasort! 

Bemenet

A standard bemenet első sorában a ládák száma van (1≤N≤10 000). A második sor pontosan N karaktert tartalmaz (szóközök nélkül), a ládasor leírását. Minden karakter vagy 'A', vagy 'B' vagy 'C'. 

Kimenet

A standard kimenet első és egyetlen sorába azt a legkisebb K számot kell írni, amelyre a bemeneti ládasor összepakolható K ládába!

Példa

Bemenet  Kimenet
10
ABACACBCCA
6


Tesztadatok

További tesztadatok a mester.inf.elte.hu oldalon.

Címkék

A feladat forrása: mester.inf.elte.hu, Haladó > Mohó algoritmusok > ABC Ládapakolás
Algoritmusok: mohó algoritmus

megoldás