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 |