Fork me on GitHub

teddy online judge

teddy es un oso de peluche

70. El rival mas debil

Limite de tiempo : 10 seg.   Total runs : 62  Aceptados : 13

Graccolin es un amante del Coliseo. Desde pequeño ha querido tener su propio equipo de gladiadores compitiendo en el gran Coliseo Romano. Sin embargo, su padre Martevious siempre quiso que su hijo fuera un gran filósofo y por eso lo mandó a estudiar con el gran Omaropous quién le enseño matemáticas, lógica, geometría y cómo preparar unos martinis secos que James Bond mismo envidiaría, si hubiera nacido 2,000 años antes. Gracolin soñaba siempre con competir en el Coliseo cuando terminara sus estudios. Poco se imaginaba que la filosofía podría ser útil para competencias. En fin, que Graccolin, luego de haberse graduado, o casi, de sus estudios con Omaropous, se ha comprado su propio equipo de gladiadores para competir en el Coliseo. Sin embargo, tantos años de estudio le dieron a Graccolin una forma distinta de pensar. Se dió cuenta muy pronto que podía estudiar de forma sistemática las probabilidades de ganar en el Coliseo. Y así es como Graccolin comenzó a desarrollar un algoritmo para estimar si debería competir contra otro equipo o no. Las reglas del coliseo son las siguientes. Una batalla entre dos equipos resulta en un equipo ganador. Cada equipo tiene una cierta cantidad de gladiadores y se llevan a cabo varios combates. Cuando un combate va a realizarse, se escogen al azar un gladiador de cada equipo. Gana el gladiador que tenga más habilidad, y le da un punto a su equipo. Tanto el perdedor como el ganador regresan a sus cuarteles y pueden ser escogidos en el siguiente combate sin que sus habilidades se vean disminuídas. Si los dos gladiadores tienen la misma habilidad, ningún punto es ganado. Graccolin sabe que por el factor de azar, es imposible saber a ciencia cierta qué equipo ganará, pero sin embargo tiene una idea de cómo estimar si sus posibilidades de ganar son de más del 50%. Gracolin sólo aceptará retos de equipos contra los que tiene más del 50% de probabilidades de ganar.

Problema

Tu labor es realizar un algoritmo que, dadas las habilidades de los gladiadores del equipo de Graccolin (dadas por números enteros no negativos), y las habilidades de los gladiadores de los equipos con los que competiría, decida si Graccolin debe o no aceptar el reto. Es decir, si tiene más del 50% de probabilidades de ganar. Para saber si un equipo tiene más de 50% de probabilidades de ganar, se toman todos los posibles combates (un gladiador de cada equipo) y se calculan cuántos combates les dan punto a uno u otro equipo. El equipo que tendría más puntos si todos los posibles combates se efectuaran una vez es el que tiene mayor probabilidad de ganar.

Entrada

La primer linea contiene un entero P que indica el numero de casos de prueba. Cada caso consiste de varias líneas de texto. En la primera se encuentra el número de equipos retadores (0 < R < 1000). Luego, la descripción del equipo de Graccolin dada por varios números separados por espacios. El primer número es la cantidad (0 < N < 10000) de gladiadores en su equipo. A continuación se dan las habilidades de cada uno de sus N gladiadores (0 ≤ H_i ≤ 100). De la tercera a la línea R+2, se encuentran las descripciones de los equipos retadores en el mismo formato que el equipo de Graccolin.

Salida

La salida debe tener R líneas, cada una con la palabra "Aceptar" o "Rechazar" (sin comillas) dependiendo de si Graccolin debe aceptar o rechazar el reto del el equipo correspondiente.

1
2 
6 1 2 4 4 4 5 
5 0 0 4 10 12 
6 1 2 4 4 4 3
Rechazar 
Aceptar

Autor: Edgar Dueñez Guzmán, Hardvard University

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