|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #12Ended |
D - Juego de Pilas
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Vicky y Mickey han decidido jugar un juego cuyas reglas son las siguientes:
Hay $N$ pares de montones de piedras de tal forma que los dos montones de un par contienen la misma cantidad de piedras, digamos $M$. Por ejemplo $(3, 3), (12, 12), (70, 70)$ son 3 pares de montones de piedras. Vicky y Mickey toman turnos alternadamente ejecutando la siguiente acción, con Vicky jugando siempre de primero.
1. Seleccionar cualquier par en el cual cada montón contenga más de una piedra y transferir una cantidad positiva de ellas hacia el otro montón. Ahora uno de los montones es más pequeño que el otro.
2. Si el número de piedras transferidas es menor o igual que $\lfloor{M/2}\rfloor$, donde $M$ es el número de piedras en cada montón del par antes de la transferencia, entonces se puede reemplazar cada montón con el más pequeño o con el más grande del par (a decisión), sino ambos montones deben ser reemplazados por el más grande del par, volviendo a tener ambos montones nuevamente la misma cantidad de piedras. Sin embargo, el número total de reemplazos por montones más grandes debe ser menor o igual al de reemplazos por montones más pequeños para cada jugador.
3. El jugador que no pueda realizar jugadas pierde el juego.
Dada la configuración inicial de cada par, prediga el ganador.
Hay $N$ pares de montones de piedras de tal forma que los dos montones de un par contienen la misma cantidad de piedras, digamos $M$. Por ejemplo $(3, 3), (12, 12), (70, 70)$ son 3 pares de montones de piedras. Vicky y Mickey toman turnos alternadamente ejecutando la siguiente acción, con Vicky jugando siempre de primero.
1. Seleccionar cualquier par en el cual cada montón contenga más de una piedra y transferir una cantidad positiva de ellas hacia el otro montón. Ahora uno de los montones es más pequeño que el otro.
2. Si el número de piedras transferidas es menor o igual que $\lfloor{M/2}\rfloor$, donde $M$ es el número de piedras en cada montón del par antes de la transferencia, entonces se puede reemplazar cada montón con el más pequeño o con el más grande del par (a decisión), sino ambos montones deben ser reemplazados por el más grande del par, volviendo a tener ambos montones nuevamente la misma cantidad de piedras. Sin embargo, el número total de reemplazos por montones más grandes debe ser menor o igual al de reemplazos por montones más pequeños para cada jugador.
3. El jugador que no pueda realizar jugadas pierde el juego.
Dada la configuración inicial de cada par, prediga el ganador.
Input
Línea 1
: La pimera línea de la entrada contiene $N$: el número de pares de montones de piedras $(1 \le N \le 2^20)$.
Línea 2
: La segunda línea estará en blanco.
Línea 3 ... N+2
: Las $N$ líneas siguientes contendrán cada una un entero $n_i$: el número inicial de piedras en ambos montones del $i$-ésimo par $(1 \le n_i \le 2^{20})$.
Output
Línea 1 : Imprima "Vicky" (sin las comillas) si Vicky gana el juego, sino imprima "Mickey" (sin las comillas).
Sample test(s)
Input
1
2
Output
Vicky
Hints
HintLa configuración inicial es $\{(2, 2)\}$. Vicky gana el juego cambiando la configuración a $\{(1, 1)\}$, al no ser posible ninguna jugada.