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 ≤ 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.