Algoritmo de programación: encontrar al ganador de una competencia

Question

Competiré en la OBI (Olimpiada Brasileña de Informática, en inglés) y estoy probando algunos ejercicios de los últimos años. Pero no puedo encontrar una solución para este ejercicio (lo traduje, lo que puede haber algunos errores):

Competencia chocolate

Carlos y Paula acaba de conseguir una bolsa de bolas de chocolate. A medida que comerían todo demasiado rápido, hicieron una competición:

• Comerán alternativamente, una después de la otra (Paula comienza siempre).
• Cada vez, solo pueden comer de 1 a M bolas, M decidido por la madre de Paula, para que no se ahoguen.
• Si uno comió K bolas en su turno, el siguiente no puede comer K bolas.
• Quien no puede jugar según las reglas anteriores pierde.

En el siguiente ejemplo, con M = 5 y 20 bolas, Carlos ha ganado:

Who plays  How many ate  Balls left 

            20 
Paula   5     15 
Carlos   4     11 
Paula   3     8 
Carlos   4     4 
Paula   2     2 
Carlos   1     1 

Tenga en cuenta que, al final, Carlos no podía comer 2 bolas para ganar, porque Paula se comió 2 en su último turno. Pero Paula no pudo comer la última pelota, porque Carlos comió 1 en su último turno, por lo que Paula no puede jugar y pierde.

Ambos son muy inteligentes y funcionan de manera óptima. Si hay una secuencia de turnos que le asegure la victoria independientemente de los turnos del otro, él/ella jugará estas secuencias.

Tarea:

Su tarea es averiguar quién va a ganar la competición si ambos juegan de manera óptima.

de entrada:

La entrada contiene sólo un único grupo de prueba, que se debe leer de la entrada estándar (normalmente el teclado).

La entrada tiene 2 enteros N (2 ≤ N ≤ 1000000) y M (2 ≤ M ≤ 1000), siendo N el número de bolas y M el número permitido por turno.

Salida:

Su programa debe imprimir, en la salida estándar, una línea que contiene el nombre del ganador.

Ejemplos:

Input:   Output: 
5 3    Paula 
20 5   Carlos 
5 6    Paula 

que han estado tratando de resolver el problema, pero no tienen idea de cómo.

Una solución en C se puede encontrar aquí: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt Pero no puedo entender el algoritmo. Alguien publicó una pregunta sobre este problema en otro sitio, pero nadie respondió.

¿Podría explicarme el algoritmo?

Éstos son los resultados esperados del programa: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

Digamos que tenemos una función booleana FirstPlayerWin (FPW) que toma dos argumentos: número de chocolates restantes (c) y el último movimiento (l) es decir, el número de chocolates tomados en la ronda anterior, que es 0 en el primer movimiento. La rutina devuelve verdadero si y solo si el primer jugador en jugar en esta situación tiene garantizada una victoria.

El caso base es que FPW (0, l) = false para cualquier l! = 1

De lo contrario, para calcular FPW (c, l), FPW (c, l) es verdadero si para cualquier x < = M, x < = c, x! = L, FPW (c - x, x) es falso. De lo contrario, es falso. Aquí es donde patea la programación dinámica, porque ahora el cálculo de FPW se reduce al cálculo de FPW para valores más pequeños de c.

Sin embargo, almacenar las entradas para esta formulación requeriría entradas de la tabla N * M, mientras que la solución que usted señala usa solo entradas de la tabla 2N.

La razón de esto es que si FPW (c, 0) es verdadero (el primer jugador gana si cualquier movimiento está disponible en chocolate cuenta c) pero FPW (c, x) es falso para x> 0, FPW (c , y) for y y! = x debe ser verdadero. Esto es porque si negar el movimiento x hace que el jugador pierda, es decir, que el jugador gane solo jugando x, entonces el movimiento x está disponible cuando y está prohibido en su lugar. Por lo tanto, es suficiente almacenar para cualquier recuento 'c' como máximo un movimiento prohibido que hace que el jugador pierda allí. De modo que puede refactorizar el problema de programación dinámica para que en lugar de almacenar la matriz bidimensional completa FPW (c, x) tenga dos matrices, una almacena los valores FPW (c, 0) y la otra almacena los movimientos prohibidos únicos que causan el primer jugador en perder en lugar de ganar, en su caso.

Cómo llegar al texto exacto del programa C citado se deja como un ejercicio para el lector.

Answer 2

Creo que éste es otro ejercicio encubierto, en la programación dinámica. El estado del juego se describe por dos cantidades: el número de bolas restantes y el número de bolas consumidas en el movimiento anterior. Cuando el número de bolas restantes es < = M, el juego se gana (si el número restante no es igual al número comido en el movimiento anterior) o se pierde (si lo es, no se puede comer todas las bolas, y tu oponente puede comer las bolas que salgas).

Si ha calculado la situación de ganar/perder para todos los números de bolas hasta H, y todos los posibles números de pelotas comidos por el jugador anterior y anotados en una tabla, puede encontrar las respuestas para todos los números de bolas hasta H + 1. Un jugador con H + 1 bolas yk bolas comido en el movimiento anterior considerará todas las posibilidades - coma i bolas para i = 1 a M excepto por el valor ilegal de k, dejando una posición con H + 1-i bolas y una anterior movimiento de i. Pueden usar la tabla que da la situación de ganar-perder para hasta H bolas restantes para tratar de encontrar una k legal que les dé una victoria. Si pueden encontrar tal valor, la posición H + 1/k es un triunfo. Si no, es una pérdida, por lo que pueden extender la tabla para cubrir hasta H + 1 bolas, y así sucesivamente.

No he trabajado con todos los códigos de ejemplo sin comentar, pero parece que podría estar haciendo algo como esto: usar una programación dinámica como recursión para construir una tabla.