Problema Final ANPA 08. Varianzas de Limogochis
Hola de nuevo a todos!
Se acerca el ANPA 09, les presentamos uno de los problemas de la final, agradecemos a Darkmars por su aportación.
Historia
Los limogochis silvestres (los que vive en vecindades), como seres amigables que son, viven en comunidades enormes con l individuos de todas las edades. Sin embargo, siempre que van a dormir, prefieren dividirse en dos grupos: A y B. Cada grupo esta formado por miembros cuya edad es similar y siempre hay al menos un limogochi en cada grupo.
De alguna forma misteriosa, cada limogochi decide a qué grupo ir y por increíble que parezca, al calcular la varianza de las edades, de cada grupo, y sumarles (la varianza del grupo Amás la varianza del grupo B). el resultado es mínimo y no hay posibilidad de alcanzar una menor suma de varianzas.
Recordemos un poco las fórmulas de la varianza y media que vimos en primaria. Si el grupo A teine k limogochis y en el grupo B hay m, entoncessu varianza grupal se calcularía como:
donde ai representa la edad de limogochi i del grupo A y B, la edad del limogochi i del grupo B. Además μA y μB son las medidas de las edades del grupo A y B respectivamente. Esto es:
Problema
Dada las edades de l limogochis, encontrar la minima varianza grupal σ.
Entrada
En la primera línea viene un único valor n que representa el números de casos de prueba contenidos en el archivo. Los casos de prueba están separados, entre ellos, por una línea en blanco. Cada caso de prueba se compone de dos líneas. La primera línea tiene un único valor entero que representa a 1 <l<2,000,000. En la segunda línea viene l enteros 0 ≤ ei ≤ 300 separados por un espacio y representan la edad de los limogochis.
Salida
Se esperan n líneas con un único valor flotante, de tres decimales de precisión, que representa la mínima varianza grupal que pueden tener los lomigochis en cada caso de prueba.
