Estación Balanceada |
La Estación Espacial Internacional contiene muchas centrifugadoras en sus laboratorios. Cada centrifugadora tiene un número de contenedores, C, en los que se pueden meter 0, 1 o 2 ratones. En total, hay S ratones, que pueden tener pesos distintos. Debes escribir un programa que asigne a cada ratón un contenedor (como máximo 2 ratones por contenedor) intentando balancear los pesos de los ratones asignados a los contenedores de la centrifugadora. En concreto, debes minimizar la expresión IMBALANCE definida de la siguiente manera.
donde:
La entrada contendrá varios casos de prueba. La primera línea de cada caso
contiene dos números. El primer número (
) define el número de contenedores de la centrifugadora, y el segundo número (
) define el número de ratones en este caso. La segunda línea de
cada caso contiene S enteros, que representan las masas de los ratones, entre 1
y 1000, separados por espacios.
Para cada caso de prueba, debes escribir en primer lugar una línea con el formato "Set #X" donde "X" es el número del caso (empezando en 1).
Las siguientes C líneas contendrán el número de contenedor, dos puntos ":", seguido de las masas de los ratones que tu programa ha asignado a ese contenedor, separadas por espacios.
A continuación, el programa debe estribir en una línea ``IMBALANCE = X" donde X es el balanceo total (definido arriba) con 5 dígitos decimales de precisión.
Las salidas de los diferentes casos se deben separar con una línea en blanco (ver el formato abajo).
2 3 6 3 8 3 5 51 19 27 14 33 5 9 1 2 3 5 7 11 13 17 19
Set #1 0: 6 3 1: 8 IMBALANCE = 1.00000 Set #2 0: 51 1: 19 27 2: 14 33 IMBALANCE = 6.00000 Set #3 0: 1 17 1: 2 13 2: 3 11 3: 5 7 4: 19 IMBALANCE = 11.60000