III Copa UHEnded |
En una fábrca hay $N$ hombres y $M$ diferentes tareas de trabajo para ellos. Se le da una matriz $A$ en donde $A_{i,j}=1$ si $i$-ésimo trabajador está calificado para completar el $j$-ésimo trabajo, y $A_{i,j} = 0$ en caso contrario. Un trabajador puede ser asignado a un trabajo sólo si está calificado para completar ese trabajo.
Su
objetivo es asignar los trabajadores a puestos de trabajo de tal
manera que la distribución de las cantidades de trabajos realizados por los trabajadores es lo más parecido posible al uniforme (en métrica euclidiana). Esto significa que el vector $N$-dimensional en el que $i$-ésimo elemento es la cantidad de trabajos asigados al $i$-ésimo trabajador, debe estar lo más cerca posible del vector $N$-dimensional en el que cada elemento es igual al número real $M / N$.
Un requisito adicional es que cada trabajo que pueda ser completado de alguna forma debe ser asignado a exactamente un trabajador.
La primera línea de entrada contiene dos números enteros $N$ y $M$ $(1 \leq N, M \leq 300)$.
Es seguido por $N$ líneas, las cuales contienen $M$ caracteres, cada uno de ellos es $0$ ó $1$. Estas líneas representan la matriz $A$.
Imprimir $N$ líneas. En la $i$-ésima línea imprima la cantidad de trabajos asignados al $i$-ésimo trabajador.