Código acm.uva.es: 410
 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.

displaymath38

donde:

tex2html_wrap_inline40
es el peso de los ratones asignados al contenedor i (o, mejor dicho, la masa, porque están en el espacio).
AM
es la media de las masas de todos los contenedores, es decir la suma de los pesos de los ratones dividido por C.

Entrada

La entrada contendrá varios casos de prueba. La primera línea de cada caso contiene dos números. El primer número ( tex2html_wrap_inline50 ) define el número de contenedores de la centrifugadora, y el segundo número ( tex2html_wrap_inline52 ) 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.

Salida

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).

Ejemplo de entrada

2 3
6 3 8
3 5
51 19 27 14 33
5 9
1 2 3 5 7 11 13 17 19

Ejemplo de salida

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