Encuentra el ganador en el juego de N bolas, en el que un jugador puede eliminar cualquier bola en el rango [A, B] en un solo movimiento

Dados dos números enteros A y B , y dado también que Alicia y Bob están jugando un juego que comienza con una bolsa que contiene N bolas, en el que, en un solo movimiento, un jugador puede sacar cualquier número de bolas entre el rango [A, B] y si el jugador no puede quitar ninguna bola, entonces el jugador pierde, la tarea es encontrar el ganador del juego si Alice y Bob juegan alternativa y óptimamente y Alice comienza el juego.

Ejemplos:

Entrada: N = 2, A = 1, B = 1
Salida: Bob
Explicación: 
Una forma en la que se puede jugar el juego es:

1. Alice quita 1 bola, por lo que las bolas restantes son 1.
2. Ahora, Bob quita la última bola.
3. Alice no puede quitar ninguna bola, por lo que pierde.

Entrada: N = 3, A = 1, B = 2
Salida: Bob

Enfoque ingenuo: el enfoque más simple es encontrar el número de Grundy para cada estado y encontrar los estados ganadores y perdedores utilizando Sprague – Teorema de Grundy .

Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

1. En primer lugar, se puede observar que (A + B) siempre está en estado perdedor, porque cualquiera que sea el número X ( A ≤ X ≤ B) de bolas que elija el jugador actual, el oponente siempre puede vaciar la bolsa ya que habrá (A + B – X) número de bolas que quedan donde A ≤ (A + B – X) ≤ B .
2. Además, a partir de observaciones anteriores, se puede observar que, para cualquier múltiplo de (A + B) , por ejemplo, m*(A + B), el oponente siempre puede reducir al jugador actual a un estado de (m – 1)*(A + B) y de (m – 1)*(A + B) a (m – 2)*(A + B) y así sucesivamente.
3. Por lo tanto, extendiendo la observación anterior, se puede decir que para cualquier múltiplo de (A + B), el oponente siempre puede reducir al jugador actual a un estado de exactamente (A + B) , que de hecho es un estado perdedor. Por lo tanto, todos los múltiplos de (A + B) son un estado perdedor.
4. Entonces, la opción óptima para cualquier jugador es reducir al oponente a un múltiplo de (A + B), porque después de esto, el jugador siempre puede ganar, sin importar cuáles sean los movimientos del oponente.
5. Entonces, ahora los estados perdedores son los estados desde los cuales uno nunca puede reducir al oponente a un múltiplo de (A + B) .
6. Por lo tanto, cualquier jugador con el estado de la forma: ((A + B)*m + y) , donde (0 ≤ y ≤ A-1) nunca puede obligar al oponente a reducir a un múltiplo de (A + B), ya que cualquier jugador solo puede elegir al menos A y como máximo B número de bolas.

Siga los pasos a continuación para resolver el problema:

• Si N%(A+B) es menor que A, imprima “ Bob ”.
• De lo contrario, escriba » Alicia «.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the winner of the
// game
string NimGame(int N, int A, int B)
{
    // Stores sum of A and B
    int sum = A + B;
 
    // If N is of the form
    // m*(A+B)+y
    if (N % sum <= A - 1)
        return "Bob";
    // Otherwise,
    else
        return "Alice";
}
 
// Driver code
int main()
{
    // Input
    int N = 3, A = 1, B = 2;
    // Function call
    cout << NimGame(N, A, B) << endl;
 
    return 0;
}

// Java Program for the above approach
import java.io.*;
 
class GFG
{
 
  // Function to find the winner of the
  // game
  public static String NimGame(int N, int A, int B)
  {
 
    // Stores sum of A and B
    int sum = A + B;
 
    // If N is of the form
    // m*(A+B)+y
    if (N % sum <= A - 1)
      return "Bob";
 
    // Otherwise,
    else
      return "Alice";
  }
 
  public static void main (String[] args)
  {
 
    // Input
    int N = 3, A = 1, B = 2;
 
    // Function call
    System.out.println(NimGame(N, A, B));
 
  }
}
 
  // This code is contributed by Potta Lokesh

# Python3 program of the above approach
 
# Function to find the winner of the game
def NimGame(N, A, B):
     
    # Stores sum of A and B
    sum = A + B
     
    # If N is of the form
    # m*(A+B)+y
    if (N % sum <= A - 1):
        return "Bob"
         
    # Otherwise,
    else:
        return "Alice"
 
# Driver code
 
# Input
N = 3
A = 1
B = 2
 
# Function call
print(NimGame(N, A, B))
 
# This code is contributed by amreshkumar3

// C# program of the above approach
using System;
 
class GFG{
 
// Function to find the winner of the
// game
public static String NimGame(int N, int A, int B)
{
     
    // Stores sum of A and B
    int sum = A + B;
     
    // If N is of the form
    // m*(A+B)+y
    if (N % sum <= A - 1)
        return "Bob";
     
    // Otherwise,
    else
        return "Alice";
}
 
// Driver code
static void Main()
{
     
    // Input
    int N = 3, A = 1, B = 2;
     
    // Function call
    Console.Write(NimGame(N, A, B));
}
}
 
// This code is contributed by SoumikMondal

<script>
        // JavaScript program for the above approach
 
        // Function to find the winner of the
        // game
        function NimGame(N, A, B) {
            // Stores sum of A and B
            let sum = A + B;
 
            // If N is of the form
            // m*(A+B)+y
            if (N % sum <= A - 1)
                return "Bob";
            // Otherwise,
            else
                return "Alice";
        }
 
        // Driver code
 
        // Input
        let N = 3, A = 1, B = 2;
        // Function call
        document.write(NimGame(N, A, B) + "<br>");
 
  // This code is contributed by Potta Lokesh
    </script>

Bob

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)