Juego de N piedras donde cada jugador puede quitar 1, 3 o 4

Dos jugadores están jugando un juego con n piedras, donde el jugador 1 siempre juega primero. Los dos jugadores se mueven en turnos alternos y se juega de manera óptima. En un solo movimiento, un jugador puede quitar 1, 3 o 4 piedras del montón de piedras. Si un jugador no puede hacer un movimiento, ese jugador pierde el juego. Dado el número de piedras donde n es menor que igual a 200, encuentra e imprime el nombre del ganador.
Ejemplos: 
 

Input : 4
Output : player 1

Input : 7
Output : player 2

Para resolver este problema, necesitamos encontrar cada valor posible de n como una posición ganadora o perdedora. Dado que el juego anterior es uno de los juegos combinatorios imparciales , la caracterización de posición perdedora y ganadora es válida.
Las propiedades características de los estados ganadores y perdedores son: 
 

• Todas las posiciones terminales son posiciones perdedoras.
• Desde cada posición ganadora, hay al menos un movimiento hacia una posición perdedora.
• Desde cada posición perdedora, cada movimiento es hacia una posición ganadora.

Si un jugador es capaz de hacer un movimiento tal que el siguiente movimiento sea el estado perdedor, entonces el jugador está en estado ganador. Encuentre el estado del jugador 1, si el jugador 1 está en estado ganador, entonces el jugador 1 gana el juego, de lo contrario, el jugador 2 ganará. 
Considere las siguientes posiciones base: 
 

1. La posición 0 es el estado perdedor, si el número de piedras es 0, entonces el jugador 1 no podrá hacer un movimiento, por lo tanto, el jugador 1 pierde.
2. La posición 1 es el estado ganador, si el número de piedras es 1, entonces el jugador 1 quitará la piedra y ganará el juego.
3. La posición 2 es el estado perdedor, si el número de piedras es 2, el jugador 1 quitará 1 piedra y luego el jugador 2 quitará la segunda piedra y ganará el juego.
4. La posición 3 es el estado ganador, si el jugador puede realizar un movimiento tal que el siguiente movimiento sea el estado perdedor y el jugador esté en el estado ganador, el jugador 1 eliminará las 3 piedras.
5. la posición 4 es el estado ganador, si el jugador puede realizar un movimiento tal que el siguiente movimiento sea el estado perdedor y el jugador esté en el estado ganador, el jugador 1 eliminará las 4 piedras
6. la posición 5 es el estado ganador, si el jugador puede realizar un movimiento tal que el siguiente movimiento sea el estado perdedor y el jugador esté en el estado ganador, el jugador 1 eliminará 3 piedras dejando 2 piedras, que es el estado perdedor
7. la posición 6 es el estado ganador, si el jugador puede realizar un movimiento tal que el siguiente movimiento sea el estado perdedor y el jugador esté en el estado ganador, el jugador 1 eliminará 4 piedras dejando 2 piedras, que es el estado perdedor
8. la posición 7 es el estado perdedor, si el número de piedras es 7, entonces el jugador 1 puede quitar 1, 3 o 4 piedras, lo que lleva al estado perdedor, por lo tanto, el jugador 1 perderá. 
    

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find winner of
// the game of N stones
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 200;
 
// finds the winning and losing
// states for the 200 stones.
void findStates(int position[])
{
    // 0 means losing state
    // 1 means winning state
    position[0] = 0;
    position[1] = 1;
    position[2] = 0;
    position[3] = 1;
    position[4] = 1;
    position[5] = 1;
    position[6] = 1;
    position[7] = 0;
 
    // find states for other positions
    for (int i = 8; i <= MAX; i++) {
        if (!position[i - 1] || !position[i - 3]
            || !position[i - 4])
            position[i] = 1;
        else
            position[i] = 0;
    }
}
 
// driver function
int main()
{
    int N = 100;
    int position[MAX] = { 0 };
 
    findStates(position);
 
    if (position[N] == 1)
        cout << "Player 1";
    else
        cout << "Player 2";
 
    return 0;
}

// Java program for the variation
// in nim game
class GFG {
     
    static final int MAX = 200;
     
    // finds the winning and losing
    // states for the 200 stones.
    static void findStates(int position[])
    {
         
        // 0 means losing state
        // 1 means winning state
        position[0] = 0;
        position[1] = 1;
        position[2] = 0;
        position[3] = 1;
        position[4] = 1;
        position[5] = 1;
        position[6] = 1;
        position[7] = 0;
     
        // find states for other positions
        for (int i = 8; i < MAX; i++) {
             
            if (position[i - 1]!=1 ||
                    position[i - 3]!=1
                  || position[i - 4]!=1)
                position[i] = 1;
            else
                position[i] = 0;
        }
    }
     
    //Driver code
    public static void main (String[] args)
    {
         
        int N = 100;
        int position[]=new int[MAX];
     
        findStates(position);
     
        if (position[N] == 1)
            System.out.print("Player 1");
        else
            System.out.print("Player 2");
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to find winner of
# the game of N stones
 
MAX = 200
 
# finds the winning and losing
# states for the 200 stones.
def findStates(position):
 
    # 0 means losing state
    # 1 means winning state
    position[0] = 0;
    position[1] = 1;
    position[2] = 0;
    position[3] = 1;
    position[4] = 1;
    position[5] = 1;
    position[6] = 1;
    position[7] = 0
 
    # find states for other positions
    for i in range(8,MAX+1):
        if not(position[i - 1]) or not(position[i - 3]) or not(position[i - 4]):
            position[i] = 1;
        else:
            position[i] = 0;
     
#driver function
N = 100
position = [0] * (MAX+1)
 
findStates(position)
 
if (position[N] == 1):
        print("Player 1")
else:
        print("Player 2")
 
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program for the variation
// in nim game
using System;
 
class GFG {
     
    static int MAX = 200;
     
    // finds the winning and losing
    // states for the 200 stones.
    static void findStates(int []position)
    {
         
        // 0 means losing state
        // 1 means winning state
        position[0] = 0;
        position[1] = 1;
        position[2] = 0;
        position[3] = 1;
        position[4] = 1;
        position[5] = 1;
        position[6] = 1;
        position[7] = 0;
     
        // find states for other positions
        for (int i = 8; i < MAX; i++)
        {
            if (position[i - 1] != 1
                  || position[i - 3] != 1
                   || position[i - 4]!=1)
                position[i] = 1;
            else
                position[i] = 0;
        }
    }
     
    // Driver code
    public static void Main ()
    {
        int N = 100;
        int []position = new int[MAX];
     
        findStates(position);
     
        if (position[N] == 1)
            Console.WriteLine("Player 1");
        else
            Console.WriteLine("Player 2");
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP  program to find winner of
// the game of N stones
$MAX = 200;
 
// finds the winning and losing
// states for the 200 stones.
function  findStates($position)
{
    global $MAX;
    // 0 means losing state
    // 1 means winning state
    $position[0] = 0;
    $position[1] = 1;
    $position[2] = 0;
    $position[3] = 1;
    $position[4] = 1;
    $position[5] = 1;
    $position[6] = 1;
    $position[7] = 0;
 
    // find states for other positions
    for ($i = 8; $i <= $MAX; $i++) {
        if (!$position[$i - 1] || !$position[$i - 3]
            || !$position[$i - 4])
            $position[$i] = 1;
        else
            $position[$i] = 0;
    }
}
 
// driver function
 
    $N = 100;
    $position[$MAX] = array(0);
 
    findStates($position);
 
    if ($position == 1)
         echo  "Player 1";
    else
        echo  "Player 2";
 
 
#This code is contributed by ajit
?>

<script>
 
// Javascript program for the variation
// in nim game
 
     let MAX = 200;
       
    // finds the winning and losing
    // states for the 200 stones.
    function findStates(position)
    {
           
        // 0 means losing state
        // 1 means winning state
        position[0] = 0;
        position[1] = 1;
        position[2] = 0;
        position[3] = 1;
        position[4] = 1;
        position[5] = 1;
        position[6] = 1;
        position[7] = 0;
       
        // find states for other positions
        for (let i = 8; i < MAX; i++)
        {
            if (position[i - 1] != 1
                  || position[i - 3] != 1
                   || position[i - 4]!=1)
                position[i] = 1;
            else
                position[i] = 0;
        }
    }
     
// Driver code
 
        let N = 100;
        let position = [];
       
        findStates(position);
       
        if (position[N] == 1)
            document.write("Player 1");
        else
            document.write("Player 2");
   
  // This code is contributed by code_hunt.
</script>

Producción: 
 

Player 2

Complejidad de tiempo: O (MAX)

Complejidad espacial : O(1)

Este artículo es una contribución de ARSHPREET_SINGH . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.