Konténerek

A rakparton hatalmas konténereket tárolnak, amiket végül mind hajóra pakolnak és elszállítanak. A konténerek a rakpartra közúton és vasúton érkeznek, és érkezési sorrendben kerülnek raktározásra, halmokban egymásra pakolva.

A tengerjáró hajók egyszerre sok konténert tudnak szállítani. A hajók berakodási ideje részben attól függ, hol találhatók az általa szállítandó konténerek. Ez az idő nő, ha a konténer nem valamelyik halom tetején található, mivel akkor meg kell várni, míg a fölötte lévő konténereket berakodják.

Szükségünk lenne egy olyan tervre, amivel a berakodási idő csökkenthető. A terv lényege, hogy hajóra csak a halmok tetején lévő konténert lehet tenni, mindemellett minimalizálni kell a szükséges halmok számát.

A feladatban ismerjük a hajók berakodási sorrendjét és a konténerek érkezési sorrendjét. Minden hajót egy nagybetűvel reprezentálunk A-tól Z-ig, és a hajókat mindig betűrendben rakodják. Minden konténert egy nagybetűvel címkézünk, ami azt jelöli, hogy melyik hajóra kell berakodni. Egy halomba akárhány konténer elhelyezhető.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egyetlen sorból áll, amelyben legalább 1, legfeljebb 1000 nagybetű szerepel. Ezek a karakterek a beérkező konténereket reprezentálják érkezési sorrendben. Például az ABAC sor jelentése: az érkező konténerek sorra az A, B, A és C hajókra kerülnek. Miután minden konténer megérkezett, szigorúan növekvő sorrendben rakodják be a hajókat: először az A hajót, majd a B-t stb.

A teszteseteket egy olyan sor követi, amelyben az end szó szerepel.

A kimenet specifikációja

Minden tesztesetre írd ki a teszteset sorszámát (1-essel kezdve) és a konténerek berakodás előtti tárolásához szükséges vermek minimális számát a példa outputban látható módon!

Példa bemenet

1. A 
2. CBACBACBACBACBA 
3. CCCCBBBBAAAA 
4. ACMICPC 
5. end

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Case 1: 1
2. Case 2: 3
3. Case 3: 1
4. Case 4: 4

letöltés szöveges állományként