Containers
En el terminal de carga de un puerto se deben almacenar grandes containers, los que eventualmente son
cargados en un barco para ser transportados. Los containers que llegan al puerto por tren o cami ́n, sono
apilados en el terminal hasta ser embarcados.
Los barcos cargan una gran cantidad de containers. El tiempo de carga de un barco depende de la
ubicacion en el terminal de carga, de los containers que deben ser subidos. El tiempo de carga aumenta si
el container que se debe subir al barco no está al tope de una pila, y para poder subirlo al barco hay que
primero sacar todos los containers que esten sobre él.
El terminal de carga necesita un plan para apilar los containers, de modo tal de minimizar los tiempos
de carga de los barcos. El plan debe permitir cargar cada barco, usando sólo containers que se encuentran
al tope de alguna pila, minimizando la cantidad de pilas necesarias en el terminal.
En este problema, se conoce de antemano el orden en que los barcos deben ser cargados, y el orden en que
los containers llegan al terminal. Cada barco es representado por una letra mayúscula entre A y Z (inclusive),
y los barcos son cargados en orden alfabético. Cada container esta ́ etiquetado con una letra mayáscula, que
indica en que ́ barco debe ser cargado. No hay lımite a la cantidad de containers que pueden ser puestos en
una misma pila.
Entrada
La entrada contiene múltiples casos de prueba. Cada caso consiste de una sola lınea, que contiene entre
1 y 1000 letras mayu ́sculas, representando el orden de llegadoa de un grupo de containers. Por ejemplo, la
lınea ABCA indica que el primer container que llega debe ser cargado en el barco A, el segundo en el barco B,
el tercero en el barco C, el ultimo en el barco A. Cuando estos containers han llegado al terminal, deben ser
cargados en los barcos. El primer barco en ser cargado es el A, el segundo es el B, y así sucesivamente.
Una lınea con la palabra end sigue al ultimo caso de prueba, para indicar el fin de la entrada.
́
Un ejemplo de entrada es la siguiente:
A
CBACBACBACBACBA
CCCCBBBBAAAA
end
Estos datos deben ser leıdos desde la entrada estándar, sin menues ni opciones.
Salida
Para cada caso de prueba de la entrada, su algoritmo debe imprimir el número del caso, seguido de la
cantidad mınima de pilas que se requieren armar en el terminal de carga, antes de empezar a cargar los
barcos, de modo tal de minimizar el tiempo de carga.
Para la entrada de ejemplo, la salida debiera ser:
Caso 1: 1
Caso 2: 3
Caso 3: 1
