Ganador del juego de monedas donde cada jugador tiene tres opciones

A y B están jugando un juego. Al principio hay n monedas. Dados dos números más x e y. En cada movimiento, un jugador puede elegir x o y o 1 monedas. A siempre comienza el juego. El jugador que saca la última moneda gana el juego o la persona que no puede sacar ninguna moneda pierde el juego. Para un valor dado de n, encuentre si A ganará el juego o no si ambos están jugando de manera óptima.

Ejemplos: 

Input :  n = 5, x = 3, y = 4
Output : A
There are 5 coins, every player can pick 1 or
3 or 4 coins on his/her turn.
A can win by picking 3 coins in first chance.
Now 2 coins will be left so B will pick one 
coin and now A can win by picking the last coin.

Input : 2 3 4
Output : B

Tomemos algunos valores de ejemplo de n para x = 3, y = 4. 
n = 0 A no puede sacar ninguna moneda, por lo que pierde 
n = 1 A puede sacar 1 moneda y ganar el juego 
n = 2 A solo puede sacar 1 moneda . Ahora B elegirá 1 moneda y ganará el juego 
n = 3 4 A ganará el juego al elegir 3 o 4 monedas 
n = 5, 6 A elegirá 3 o 4 monedas. Ahora B tendrá que elegir entre 2 monedas para que A gane.
Podemos observar que A gana el juego por n monedas solo cuando B pierde por n-1 monedas o nx o ny. 

// C++ program to find winner of game
// if player can pick 1, x, y coins
#include <bits/stdc++.h>
using namespace std;
 
// To find winner of game
bool findWinner(int x, int y, int n)
{
    // To store results
    int dp[n + 1];
 
    // Initial values
    dp[0] = false;
    dp[1] = true;
 
    // Computing other values.
    for (int i = 2; i <= n; i++) {
 
        // If A losses any of i-1 or i-x
        // or i-y game then he will
        // definitely win game i
        if (i - 1 >= 0 and !dp[i - 1])
            dp[i] = true;
        else if (i - x >= 0 and !dp[i - x])
            dp[i] = true;
        else if (i - y >= 0 and !dp[i - y])
            dp[i] = true;
 
        // Else A loses game.
        else
            dp[i] = false;
    }
 
    // If dp[n] is true then A will
    // game otherwise  he losses
    return dp[n];
}
 
// Driver program to test findWinner();
int main()
{
    int x = 3, y = 4, n = 5;
    if (findWinner(x, y, n))
        cout << 'A';
    else
        cout << 'B';
 
    return 0;
}

// Java program to find winner of game
// if player can pick 1, x, y coins
import java.util.Arrays;
 
public class GFG {
     
    // To find winner of game
    static boolean findWinner(int x, int y, int n)
    {
        // To store results
        boolean[] dp = new boolean[n + 1];
      
        Arrays.fill(dp, false);
     
        // Initial values
        dp[0] = false;
        dp[1] = true;
      
        // Computing other values.
        for (int i = 2; i <= n; i++) {
      
            // If A losses any of i-1 or i-x
            // or i-y game then he will
            // definitely win game i
            if (i - 1 >= 0 && dp[i - 1] == false)
                dp[i] = true;
            else if (i - x >= 0 && dp[i - x] == false)
                dp[i] = true;
            else if (i - y >= 0 && dp[i - y] == false)
                dp[i] = true;
      
            // Else A loses game.
            else
                dp[i] = false;
        }
      
        // If dp[n] is true then A will
        // game otherwise  he losses
        return dp[n];
    }
      
    // Driver program to test findWinner();
    public static void main(String args[])
    {
        int x = 3, y = 4, n = 5;
        if (findWinner(x, y, n) == true)
            System.out.println('A');
        else
            System.out.println('B');
    }
}
// This code is contributed by Sumit Ghosh

# Python3 program to find winner of game
# if player can pick 1, x, y coins
 
# To find winner of game
def findWinner(x, y, n):
     
    # To store results
    dp = [0 for i in range(n + 1)]
 
    # Initial values
    dp[0] = False
    dp[1] = True
 
    # Computing other values.
    for i in range(2, n + 1):
 
        # If A losses any of i-1 or i-x
        # or i-y game then he will
        # definitely win game i
        if (i - 1 >= 0 and not dp[i - 1]):
            dp[i] = True
        elif (i - x >= 0 and not dp[i - x]):
            dp[i] = True
        elif (i - y >= 0 and not dp[i - y]):
            dp[i] = True
 
        # Else A loses game.
        else:
            dp[i] = False
 
    # If dp[n] is true then A will
    # game otherwise he losses
    return dp[n]
 
# Driver Code
x = 3; y = 4; n = 5
if (findWinner(x, y, n)):
    print('A')
else:
    print('B')
 
# This code is contributed by Azkia Anam

// C# program to find winner of game
// if player can pick 1, x, y coins
using System;
 
public class GFG {
     
    // To find winner of game
    static bool findWinner(int x, int y, int n)
    {
         
        // To store results
        bool[] dp = new bool[n + 1];
     
        for(int i = 0; i < n+1; i++)
            dp[i] =false;
     
        // Initial values
        dp[0] = false;
        dp[1] = true;
     
        // Computing other values.
        for (int i = 2; i <= n; i++)
        {
     
            // If A losses any of i-1 or i-x
            // or i-y game then he will
            // definitely win game i
            if (i - 1 >= 0 && dp[i - 1] == false)
                dp[i] = true;
            else if (i - x >= 0 && dp[i - x] == false)
                dp[i] = true;
            else if (i - y >= 0 && dp[i - y] == false)
                dp[i] = true;
     
            // Else A loses game.
            else
                dp[i] = false;
        }
     
        // If dp[n] is true then A will
        // game otherwise he losses
        return dp[n];
    }
     
    // Driver program to test findWinner();
    public static void Main()
    {
        int x = 3, y = 4, n = 5;
         
        if (findWinner(x, y, n) == true)
            Console.WriteLine('A');
        else
            Console.WriteLine('B');
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find winner of game
// if player can pick 1, x, y coins
 
// To find winner of game
function findWinner( $x, $y, $n)
{
     
    // To store results
    $dp= array();
 
    // Initial values
    $dp[0] = false;
    $dp[1] = true;
 
    // Computing other values.
    for ($i = 2; $i <= $n; $i++)
    {
 
        // If A losses any of i-1 or i-x
        // or i-y game then he will
        // definitely win game i
        if ($i - 1 >= 0 and !$dp[$i - 1])
            $dp[$i] = true;
        else if ($i - $x >= 0 and !$dp[$i - $x])
            $dp[$i] = true;
        else if ($i - $y >= 0 and !$dp[$i - $y])
            $dp[$i] = true;
 
        // Else A loses game.
        else
            $dp[$i] = false;
    }
 
    // If dp[n] is true then A will
    // game otherwise he losses
    return $dp[$n];
}
 
// Driver program to test findWinner();
    $x = 3; $y = 4; $n = 5;
    if (findWinner($x, $y, $n))
        echo 'A';
    else
        echo 'B';
         
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to find winner of game
// if player can pick 1, x, y coins
 
// To find winner of game
function findWinner(x, y, n)
{
     
    // To store results
    var dp = Array(n + 1).fill(0);
 
    // Initial values
    dp[0] = false;
    dp[1] = true;
 
    // Computing other values.
    for(var i = 2; i <= n; i++)
    {
         
        // If A losses any of i-1 or i-x
        // or i-y game then he will
        // definitely win game i
        if (i - 1 >= 0 && !dp[i - 1])
            dp[i] = true;
        else if (i - x >= 0 && !dp[i - x])
            dp[i] = true;
        else if (i - y >= 0 && !dp[i - y])
            dp[i] = true;
 
        // Else A loses game.
        else
            dp[i] = false;
    }
 
    // If dp[n] is true then A will
    // game otherwise he losses
    return dp[n];
}
 
// Driver code
var x = 3, y = 4, n = 5;
if (findWinner(x, y, n))
    document.write('A');
else
    document.write('B');
 
// This code is contributed by noob2000
 
</script>

Producción: 

A

Este artículo es una contribución de nuclode . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.