Supongo que el objetivo es ser el último en hacer un movimiento legal, y que una vez que se hayan tomado x monedas, nunca se podrán volver a tomar x monedas de ningún montón.
Este es el primer jugador que gana si n = 1 o p es impar. La estrategia es tomar una pila completa en el primer turno, y luego, hasta que termine el juego, tomar siempre el resto de la pila de la que el segundo jugador tomó monedas. Como p es impar, [math] px \ neq x [/ math], entonces si x es una jugada legal, también lo es el resto de esa misma pila.
Eventualmente, no quedarán pilas o todas las x de 1 a p se usarán, por lo que el segundo jugador se quedará sin un movimiento legal.
- Dado que solo quedan 2 meses para las regiones regionales de ACM ICPC, ¿cuántos problemas podría resolver allí si comenzara a practicar ahora, teniendo solo la idea más básica sobre algoritmos?
- ¿Cuáles son las complejidades temporales del montón?
- Cómo encontrar la notación Big O del siguiente programa
- F (n) E de O (g (n)) donde log (g (n))> 1 yf (n)> 1 para n grande?
- Según usted, ¿cuáles son los algoritmos de aprendizaje automático más importantes en la actualidad?
Por otro lado, si p = 2 yn> 1, es la victoria de un segundo jugador: solo hay dos movimientos legales (1 moneda y 2 monedas), por lo que el juego termina después de 1 ronda.
Algunos análisis de bonificación que no se solicitaron:
n = 2, p = 4 es el primer jugador que gana. El primer jugador toma una pila completa. Si el segundo jugador toma 1 moneda, toma 3 y gana. Si el segundo jugador toma más de 1 moneda, toma 1 y gana.
n> 2, p = 4 es la victoria de un segundo jugador. Hay cuatro movimientos posibles (1 a 4 monedas) y siempre es posible tomarlos todos. No se necesita una estrategia inteligente. De hecho, n> p / 2 es siempre un segundo jugador que gana por p incluso por la misma razón.
n = 2, p = 6 es la victoria de un segundo jugador. Si el primer jugador toma 4, 5 o 6, el segundo jugador toma 3 del otro montón, dejando solo movimientos de 1 o 2 monedas, las cuales siempre se pueden tomar. Si el primer jugador toma 1 o 2, el segundo jugador toma 2 o 1 de la otra pila, dejando solo movimientos de 3, 4 o 5, pero dado que dos de ellos suman más de 5, exactamente dos de ellos pueden ser tomado. Si el primer jugador toma 3 monedas, el segundo jugador toma la segunda pila completa, dejando los dos últimos movimientos como 1 y 2 monedas en algún orden.
- n = 3, p = 6 es el primer jugador que gana. El primer jugador toma una pila completa. Se puede igualar una jugada que no sea de 3 monedas tomando el resto del montón, por lo que el segundo jugador tendrá que tomar 3 monedas antes de que se hayan usado los dos movimientos 1 y 2 o perder. Si toman 3 del segundo montón, el jugador uno toma 5 monedas del tercer montón, dejando solo los dos movimientos y la victoria. Si no lo hacen, uno de estos dos movimientos se usará en la segunda pila tomando el resto de la pila, y la otra se puede usar en las tres monedas restantes en la tercera pila.
