OMI 30° D1-P4: Mimo y Yuyú

Ver en PDF

Enviar solución

Puntos: 100 (parcial)
Límite de tiempo: 2.0s
Límite de memoria: 256M

Autor:
Tipo de problema
Lenguajes permitidos
C, C++, Java, Python

¡Mimo y Yuyú acaban de terminar su rompecabezas de 1000 piezas! Sin embargo, eso viene con su inconveniente: ya no saben qué jugar. Pero de alguna manera han conseguido inventar un juego nuevo. Para jugar este juego, se necesita de un suministro infinito de galletas María y un tablero rectangular de tamano \(n × m\). Cada celda del tablero puede contener cualquier cantidad de galletas María.

Las filas del tablero están nombradas de la 1 a la n de arriba hacia abajo. También están nombradas las columnas del tablero de la 1 a la m de izquierda a derecha. Se usará (u, v) para referirse a la celda en la fila u y columna v. Al inicio, hay k galletas María, la \(i-ésima\) galleta María está ubicada en (x_i , y_i).

Mimo y Yuyú ahora juegan el juego alternando turnos. En su turno, el jugador elige una galleta María g que esté actualmente en el tablero y, al mismo tiempo, elige un camino de celdas distintas (a_1 , b_1), (a_2 , b_2), . . . (a_p , b_p) tal que se cumplan las siguientes condiciones:

  • p \geq 2
  • g tiene que estar en la celda (a_1 , b_1)
  • Para toda i (1 \leq i \leq p), |a_i + 1 - a_i| + |b_i + 1 - b_i| = 1. Es decir, cualquier par de celdas que sean adyacentes en la secuencia lo tienen que ser en el camino.
  • b_1 \geq b_2 \geq . . . \geq b_p. Es decir, las columnas de las celdas del camino tienen que formar una secuencia no-aumentante.
  • b_p = 1. Es decir, la ´ultima celda del camino tiene que pertenecer a la columna 1.
  • b_1 > b_2. De hecho, b_2 = b_1 - 1. Es decir, (a_1 , b_1) tiene que ser la ´unica celda del camino que pertenece a la columna b_1.

Luego, se come la galleta g del tablero y añade 1 galleta Marpia a cada una de las celdas (a_2 , b_2), (a_3 , b_3), . . . (a_p , b_p). Esto concluye su turno.

En el juego, pierde quien no puede hacer ningún movimiento (es decir, que no puede elegir ninguna galleta María g junto con una secuencia que cumpla todas las condiciones). Tanto Mimo como Yuyú son muy competitivos, y no cometerán ningún error al jugar; es decir, juegan óptimamente. Determina quién gana si Mimo empieza jugando.

Por ejemplo, considera un juego donde n = 6, m = 4, y existen actualmente 3 galletas Marías en (2, 3), (4, 2) y (6, 4) (como se ve en la Figura 1). Un turno válido podría ser elegir g como la galleta María en (6, 4) y la sequence de celdas con p = 10 definida por a = [6, 6, 5, 4, 3, 2, 2, 3, 4, 4] y b = [4, 3, 3, 3, 3, 3, 2, 2, 2, 1].

Para efectos de claridad, una línea punteada se muestra en la Figura 2 que pasa a través de esta elección particular de (a_1 , b_1), (a_2 , b_2), . . . (a_p , b_p) en orden. La figura 3 y 4 muestran el estado del juego después de que ocurre el turno, con y sin el resaltado del camino respectivamente.

Explicacion de los casos

Imprime Mimo si Mimo gana, o Yuyu si Yuyú gana.

Entrada

  • La primera línea contiene t que representa el número de casos de prueba.
  • La primera línea de cada de caso de prueba contiene tres enteros n, m, y k.
  • Las \(i-ésima\) de las siguientes k líneas contienen dos enteros x_i y y_i.

Salida

Para cada caso de prueba imprime una línea: Mimo si Mimo gana, o Yuyu si Yuyú gana.

Ejemplos

Ejemplo 1

Entrada
1
2 3 2
2 2
1 3
Salida
Mimo

Ejemplo 2

Entrada
2
6 4 3
2 3
4 2
6 4
6 4 11
6 3
5 3
4 3
3 3
2 3
2 3
2 2
3 2
4 2
4 2
4 1
Salida
Mimo
Yuyu

Consideraciones

Sea S_k la suma de k sobre todos los casos de prueba.

  • 1 \leq t \leq 104.
  • \(1 \leq n, m, k \leq 2 × 10^5\).
  • \(S_k \leq 2 × 10^5\).
  • 1 \leq x_i \leq n (1 \leq i \leq k).
  • 1 \leq y_i \le m (1 \leq i \leq k).

Subtareas

  • Subtarea 1 (12 puntos): n = 2, m = 3 y k \leq 3.
  • Subtarea 2 (12 puntos): m \geq 2 y y_i = 2 (1 \leq i \leq k). Es decir, las k galletas Marías inician en la columna 2.
  • Subtarea 3 (12 puntos): k = 1.
  • Subtarea 4 (12 puntos): k = 2.
  • Subtarea 5 (12 puntos): n \geq 2 y y_i = y_j (1 \leq i, j \leq k). Es decir, las k galletas Marías inician en la misma columna.
  • Subtarea 6 (25 puntos): n = 1.
  • Subtarea 7 (15 puntos): n \geq 2.

Comentarios

No hay comentarios por el momento.