Problema A - Alien vs Depredador
Entrada: guerra.in
Salida: estándar
Máxima memoria: 32 MB
Tiempo límite: 10 segundos
Descripción
Después de una guerra sin fin, donde el resultado parcial no le conviene a ninguna de estas dos razas alienígenas: aliens y deprededadores. Han decidido crear una batalla final donde el ganador se quedará con la tierra, pero esta vez con ciertas reglas:
- Primero ellos definirán el lugar de la batalla, que tiene como área dx * dy unidades cuadradas de espacio. El lugar de batalla se divide en exactamente dx * dy regiones. La primera región es (0, 0) y la última es (dx – 1, dy – 1).
- Ellos podrán colocara lo máximo 30 guerreros por bando, cada uno en regiones distintas entre sí.
- Cada guerrero tiene asignada una fuerza mayor que cero, misma que no cambia durante toda la batalla, La suma de las fuerzas de todos los guerreros de cada bando son iguales.
- Cada guerrero tiene una estrategia de movimiento definida, con movimientos horizontales y verticales de tamaño 4; por ejemplo un guerrero con estrategia de movimiento HHVV primero peleará en la región donde estaba colocado, al día siguiente se moverá a una sección que esté en la misma fila, y al día siguiente lo mismo, y al día siguiente a una sección que esté en la misma columna. Esa estrategia de movimiento se repetirá indefinidamente.
- Los movimientos horizontales serán primero a la derecha, en caso de que no pueda continuar moviéndose a la derecha, se convierte en izquierdos. De igual forma si ya no hay más izquierdos se convierte de nuevo a la derecha.
- Los movimientos verticales serán primeros hacia abajo, en caso de que no se pueda mover más hacia abajo se convierte a movimientos hacia arriba. De igual forma si ya no hay más movimientos hacia arriba se convierte de nuevo hacia abajo.
- Si uno o más aliens se enfrentan contra uno o más depredadores en la misma región, sobreviven todos los que son parte del bando que la suma de sus fuerzas entre sus guerreros es mayor. En caso de igualdad todos mueren.
- La guerra durará exactamente t días. Después de los t días, el primer criterio de desempate es por el número de soldados que quedaron vivos por bando, gana quien tiene más soldados sin importar su fuerza. En caso de empate el que tenga mayor suma de fuerzas entre los elementos que vivieron
Por ejemplo, si un alien fue posicionado en la región (1, 1) de un campo de batalla con dimensiones 3x3, y su estrategia de movimientos es HHVV entonces se moverá de esta forma: (1, 1) > (1, 2) > (1, 1) > (2, 1) > (1, 1) > (1, 0) > (1, 1) > (0, 1) > (1, 1) … y así consecuentemente hasta que muera o termine la batalla.
Entrada
La primera línea de la entrada contendrá un número c (1 ≤ c ≤ 100) que indica el número de casos de entrada a procesar. La entrada de cada caso inicia con una línea con 5 números: dx dy na nd t separados por un espacio. Donde:
- dx(3 ≤ dx ≤ 30) indica el número de filas del campo de batalla.
- dy(3 ≤ dy ≤ 30) indica el número de columnas del campo de batalla.
- na(1 ≤ na ≤ 30) indica el número de aliens.
- nd (1 ≤ nd ≤ 30) indica el número de depredadores.
- t (1 ≤ t ≤ 1000) tiempo de la batalla.
Después de lo anterior siguen na + nd líneas. Las primeras na líneas contendrán tres enteros: Ax Ay Af seguido de una cadena Am; el par ordenado (Ax, Ay) indica la posición inicial del alien, Af la fuerza del alien y Am una cadena de exactamente cuatro caracteres con valores ‘H’ y ‘V’ que describe como se mueve el alien. Las siguientes nd líneas contendrán tres enteros Dx Dy Df seguido de una cadena Dm; el par ordenado Dx, Dy indica la posición inicial del depredador, Df la fuerza del deprededador y Dm una cadena de exactamente cuatro caracteres con valores ‘H’ y ‘V’ que describe como se mueve el depredador.
Salida
La salida consistirá de alguna de las siguientes cadenas dependiendo del resultado de la batalla:
- Aliens ganan.
- Depredadores ganan.
- Aliens y Depredadores empatan.
Ejemplo de entrada |
Ejemplo de salida |
2
3 3 1 1 10
1 1 10 HHVV
2 2 10 HVHV
3 3 1 2 10
0 0 100 HHHH
0 1 80 HHHH
0 2 20 HHHH
|
Aliens y Depredadores empatan.
Aliens ganan.
|
