Fork me on GitHub

teddy online judge

teddy es un oso de peluche

98. Organizando un Evento Infantil

Limite de tiempo : 6 seg.   Total runs : 1  Aceptados : 1

Límite de tiempo Límite de memoria Archivo de entrada Archivo de salida
6s 64Mib data.in data.out

Varios de tus invitados tienen hambre, y el pastel de fresa continúa sin ser partido. Como el dueño del salón de fiestas "Indigo, Terracota y Café", eres el encargado de resolver el conflicto de que los invitados se están peleando porque todos quieren recibir una rebanada de pastel con el mismo número de fresas, o lo más cerca que se pueda a esta cantidad. Si sabes que hay N invitados y F fresas, cada invitado espera que le toquen exactamente F/N fresas, y entre más se aleje esta cantidad del número de fresas que haya en su pedazo, más se va a enojar. Así que para minimizar el enojo colectivo de la gente, lo que quieres es encontrar una manera de partir el pastel minimizando la suma de |Fi - F/N|, donde |X| denota el valor absoluto de la expresión X, Fi es un entero que representa el número de fresas en la rebanada del i-ésimo invitado y F/N el promedio de fresas que espera recibir. Nota que este último número no necesariamente es entero.

Para que el relajo de cortar el pastel sea menor, decides que sólo vas a realizar cortes paralelos a las orillas del pastel (que, por cierto, es rectangular). Como las fresas fueron cultivadas en un rancho con certificación ISO-9000, todas tienen exactamente el mismo tamaño: 0.5cm de diámetro. El pastelero era demasiado perfeccionista, así que colocó todos los centros de las fresas en coordenadas enteras. Si te preguntabas por qué hay fresas en la misma posición x,y, la razón es que el pastel es tridimensional.


Ejemplo 1: si se cortara el pastel de manera horizontal, tendríamos un enojo total de |2 - 3| + |2 - 1| + |2 - 2| = 2. En cambio, cortándolo de manera vertical podemos generar un enojo total de |2 - 2| + |2 - 2| + |2 - 2| = 0, el cual es óptimo.

Entrada

La primer línea de la entrada contiene un entero Nc (1 ≤ Nc ≤ 100), que contiene el número de casos de prueba. Cada caso de prueba contiene dos enteros N y F (1 ≤ N ≤ 100,000, 1 ≤ F ≤ 100,000), el número de invitados y el número de fresas en el pastel. Las siguientes líneas contienen dos enteros x y y (0 ≤ x, y ≤ 1,000,000).

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido de la suma mínima de enojo de toda la gente, expresada como una fracción irreducible. Sigue el formato de ejemplo.

Entrada/Salida de ejemplo

2
6 3
3 4
6 4
8 4
2 3
5 2
10 2
6 5
3 4
6 4
8 4
2 3
5 2
10 2

Caso 1: 0/1
Caso 2: 8/5

Problema original de ACM ANARC 2009

Hecho por Alan Gonzalez @_alanboy ; Concepto Luis Hector Chavez @lhchavez ; Infraestructura por Instituto Tecnologico de Celaya

contribuciones de los usuarios bajo la licencia cc-wiki con atribucion requerida