teddy online judge

37. Empacando recipientes ecologicos

Limite de tiempo : 1 seg.   Total runs : 68  Aceptados : 33

Empacar en recipientes, o la colocación de objetos de cierto peso dentro de diferentes recipientes tiene restricciones, es un problema historicamente interesante. Algunos problemas de empaque en recipientes no son de resolución de fuerza bruta, pero pueden ser tratados con programación dinámica o solucionados optimamente con métodos heurísticos.

En este problema debes resolver un problema de empaquetado en recipientes que se trata de reciclado de vidrio.

El problema

Para reciclar vidrio se requiere que el vidrio sea separado por colores dentro de una o tres categorías: vidrio café, vidrio verde, y vidrio claro. En este problema tienes tres depósitos, cada uno conteniendo un específico número de botellas cafés, verdes y claras, con el propósito de ser recicladas, las botellas necesitan desplazarse a fin de que cada depósito contenga botellas de un solo color.

El problema es para minimizar el número de botellas que tienen que ser movidas. Puedes asumir que el problema esta en minimizar el número de movimientos entre cajas.

Para la resolución de este problema, cada recipiente tiene capacidad infinita y la única restricción es el mover las botellas a fin de que cada recipiente contenga botellas de un solo color. El número total de botellas nunca excederá 2^31.

La entrada

La entrada consiste de una serie de líneas, donde cada línea contiene 9 enteros. Los primeros tres números en una línea representan el número de botellas cafés, verdes y claras (respectivamente) en el recipiente número 1, los siguientes tres representan el número de botellas cafés, verdes y claras (respectivamente) en el recipiente número 2, y los últimos tres representan el número de botellas cafés, verdes y claras (respectivamente) en el empaque número 3. Por ejemplo: la línea 10 15 20 30 12 8 15 8 31 indica que estan 20 botellas claras en el empaque número 1, 12 botellas verdes en el empaque número 2 y 15 botellas cafés en el empaque número 3.

Los enteros en cada línea pueden estar separados por uno o más espacios. Tu programa debe procesar todas las líneas en el archivo de entrada.

La salida

Por cada línea de entrada tiene que haber una línea de salida indicando que colores de botellas van en que empaque para minimizar el número de movientos de las botellas. Debes también imprimir el mínimo número de movimientos de botellas.

Tu salida debe consistir en una cadena de los tres caracteres en mayúsculas 'G', 'B', 'C' (representado los colores verde, café y claro) representando el color asociado con cada empaque.

El primer caracter de la cadena representa el color asociado con el primer empaque, el segundo caracter de la cadena representa el color asociado con el segundo empaque, y el tercer caracter representa el color asociado con el tercer empaque.

El entero indicando el mínimo número de movimiento de botellas debe seguir a la cadena.

Si hay más de un orden de empaques cafés, verdes y claros que produce el mismo número de movimientos entonces se debe imprimir la primera cadena ordenada alfabéticamente.

Ejemplo de entrada

1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10

Ejemplo de salida

BCG 30
CBG 50