OMI 30° D1-P4: Mimo y Yuyú
Ver en PDF¡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 a la
de arriba hacia abajo. También están nombradas las columnas del tablero de la
a la
de izquierda a derecha. Se usará
para referirse a la celda en la fila
y columna
. Al inicio, hay
galletas María, la \(i-ésima\) galleta María está ubicada en
.
Mimo y Yuyú ahora juegan el juego alternando turnos. En su turno, el jugador elige una galleta María que esté actualmente en el tablero y, al mismo tiempo, elige un camino de celdas distintas
,
, . . .
tal que se cumplan las siguientes condiciones:
tiene que estar en la celda
- Para toda
,
. Es decir, cualquier par de celdas que sean adyacentes en la secuencia lo tienen que ser en el camino.
. Es decir, las columnas de las celdas del camino tienen que formar una secuencia no-aumentante.
. Es decir, la ´ultima celda del camino tiene que pertenecer a la columna
.
. De hecho,
. Es decir,
tiene que ser la ´unica celda del camino que pertenece a la columna
.
Luego, se come la galleta del tablero y añade
galleta Marpia a cada una de las celdas
,
, . . .
. 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 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 , y existen actualmente
galletas Marías en
y
(como se ve en la Figura 1). Un turno válido podría ser elegir
como la galleta María en
y la sequence de celdas con
definida por
y
.
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 ,
, . . .
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.
Imprime Mimo si Mimo gana, o Yuyu si Yuyú gana.
Entrada
- La primera línea contiene
que representa el número de casos de prueba.
- La primera línea de cada de caso de prueba contiene tres enteros
,
, y
.
- Las \(i-ésima\) de las siguientes
líneas contienen dos enteros
y
.
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 la suma de
sobre todos los casos de prueba.
.
- \(1 \leq n, m, k \leq 2 × 10^5\).
- \(S_k \leq 2 × 10^5\).
.
.
Subtareas
- Subtarea 1 (12 puntos):
,
y
.
- Subtarea 2 (12 puntos):
y
. Es decir, las
galletas Marías inician en la columna
.
- Subtarea 3 (12 puntos):
.
- Subtarea 4 (12 puntos):
.
- Subtarea 5 (12 puntos):
y
. Es decir, las
galletas Marías inician en la misma columna.
- Subtarea 6 (25 puntos):
.
- Subtarea 7 (15 puntos):
.
Comentarios