Problema ACM-ICPC. Coins on a Board


En artículos anteriores vimos una de las herramientas más poderosas para resolver algunos problemas de la teoría de juegos, los números Grundy. En este artículo utilizaremos lo aprendido y daremos solución a un problema de programación al estilo ACM-ICPC. Las especificaciones del problema son las siguientes.

Nombre: Coins on a Board

Sitio del problema: http://coj.uci.cu/24h/problem.xhtml?pid=1646

Descripción: Dos mujeres, Andrea y Vida, se enfrentan en un juego de tablero. El juego consiste en que inicialmente hay N+1 cuadrados numerados desde 0 hasta N. Las reglas son simples, inicialmente hay M monedas ubicadas en el tablero en posiciones no necesariamente diferentes. En cada turno, se toma una moneda y se hace una jugada con ella. Una jugada consiste en mover una moneda al menos un cuadrado hacia la izquierda de su posición correspondiente. El juego termina cuando todas las monedas se encuentran en la posición 0 del tablero y gana la mujer que mueve la última moneda hacia esa posición. Vida es la primera en jugar.

Especificación de entrada:

Varios casos de entrada, y por cada caso:

Línea 1: Dos enteros M y N. para 1<=N<=20 y 1<=M<=50.

Línea 2: M enteros (V1, V2,…., Vm) para 0 <=Vi<=N.

Especificación de salida:

Por cada caso imprimir una línea con una cadena, “Vida” si gana la primera mujer o “Andrea” si gana la segunda.

Ejemplo de entrada:

1 5

1

2 5

1 1

Ejemplo de salida:

Vida

Andrea

Solución:

Estamos en presencia de una suma de juegos. Es lo mismo tener todas las monedas puestas en el tablero que tener varios tableros con una moneda puesta.

Podemos demostrar que este juego es una variante de Nim, ¿cómo?, supongamos que tenemos una moneda en la posición 4. Esta la podemos mover hacia cualquier posición a su izquierda. Si de la posición 4 nos podemos mover a las posiciones 3, 2,1 y 0, es como tener un bulto con 4 piedras y poderle quitar 1, 2, 3 o 4 piedras.

Pues ahora que hemos visto como representar el problema antes visto, como una variante del juego de Nim, pasemos a calcular los valores de los números Grundy a todas las posiciones.

Para la posición p = 0 no nos podemos mover hacia ninguna parte, por lo que G(0) = 0. Desde p = 1 nos podemos mover hacia p = 0 con valor G(0), por lo que G(1) = 1.

Calculándola para todas las demás posiciones tenemos que G(n) = n, justamente igual que en Nim.

Analicemos el primer ejemplo de la entrada.

Análisis del problema

Fig1: Análisis del problema

Es una posición ganadora ya que G(1) = 1.

La jugada ganadora está en mover hacia la posición cero la moneda, por lo que gana la primera jugadora (Vida).

Segundo ejemplo de la entrada.

Análisis del problema

Fig2: Análisis del problema

Es una posición perdedora ya que G(1) xor G(1) = 0. La única jugada posible que tiene Vida es mover una moneda hacia la posición 0 dejando el juego de esta forma.

Análisis del problema

Fig3: Análisis del problema

Andrea juega la moneda de la posición 1 hacia la posición cero alcanzando un estado terminal y gana el juego.

Análisis del problema

Fig4: Análisis del problema

La solución del juego sería teniendo el número Grundy de todas las posiciones que es G(n) = n, hallamos el xor entre todas las posiciones donde haya monedas, si el resultado es mayor que cero estamos en una posición ganadora y gana Vida, y si es igual a cero estamos en una posición perdedora, por lo que gana Andrea.

Código en C++ que da solución al problema:

int main()
{
    /*Declaración de las variables m y n que se leerán en la entrada*/
    int m,n;

    /*Arreglo donde almacenaremos las posiciones de las monedas de cada caso*/
    int arr[55];
    
    /*Se lee hasta fin de fichero, dado que en el problema no especifica la cantidad de casos a leer*/
    while(scanf("%d%d",&m,&n)!= EOF)    {
        /*leer las M monedas*/
        for(int i = 0; i < m; i++)
        {
            scanf("%d", &arr[i]);//Leemos las posiciones de las monedas
        }
        int grundy = arr[0];
        for(int i = 1; i < m; i++)
        {
            grundy = (grundy ^ arr[i]); /*calculamos el xor de las pos donde están las monedas*/
        }
        
        /*Si el xor entre todos los números Grundy calculados es mayor que 0 gana Vida en caso contrario gana Andrea*/
        if(grundy==0)cout << "Andrea"<<endl;
        else cout << "Vida" << endl;
    }
    return 0;
}

Es muy importante para lograr entender la Teoría de Juegos, comprender la utilidad que tienen los números Grundy, y saber cómo llevar ciertos juegos a su variante de Nim equivalente, aplicar el teorema de Sprague-Grundy es importante a la hora de reducir juegos complicados a un simple juego de Nim.

Como sugerencia pueden ver el problema 1296- Again Stone Game del jurado online lightoj.

Aplicando todo lo visto hasta ahora sobre los números Grundy, podemos llegar a la solución de este problema en específico, próximamente veremos otros ejemplos que pueden ser resueltos por esta misma vía de solución. Cualquier duda que puedan tener, pueden reflejarla en sus comentarios. Hasta la próxima.