Encuentre el jugador que alcance al menos N multiplicando con cualquier valor del rango dado

Dado un número entero N , la tarea de dos jugadores A y B es hacer que el valor de X ( inicializado con 1 ) sea al menos N multiplicando X con cualquier número del rango [2, 9] en turnos alternos. Suponiendo que ambos jugadores jueguen de manera óptima. la tarea es encontrar el jugador para obtener un valor ≥ N primero.

Ejemplos:

Entrada: N = 12
Salida: Jugador B
Explicación: 
Inicialmente, X = 1.
A multiplica X por 9. Por lo tanto, X = 1 * 9 = 9.
En el segundo turno, B multiplica X por 2. Por lo tanto, X = 9*2 = 18
Por lo tanto, B gana.

Entrada: N = 10
Salida: Jugador B

Planteamiento: La idea es utilizar el concepto de teoría de juegos combinatorios . Encuentre las posiciones desde donde, si un número se multiplica con X conduce a la victoria y también las posiciones que conducen a una pérdida. A continuación se muestran los pasos:

• En la teoría de juegos combinatorios, definamos que una posición N es una posición desde la cual el siguiente jugador en moverse gana si juega de manera óptima y la posición P es una posición en la que el siguiente jugador en moverse siempre pierde si su oponente juega de manera óptima.
• La posición más baja que se puede alcanzar hasta N es, por ejemplo, res = ceil(N/9) . Por lo tanto, todas las posiciones desde [res, res + 1, res + 2, ….., N – 1] son ​​N posiciones.
• Las únicas posiciones que se ven obligadas a moverse a [res, res + 1, …, (N – 1)] son ​​aquellas que cuando se multiplican por 2 , y se encuentran en ese intervalo, que viene dado por Y = ceil(res/2 ) ,
• Por lo tanto, [Y, Y + 1, …, (res – 1)] son ​​todas las posiciones P.
• Después de repetir los pasos anteriores hasta encontrar el intervalo que contiene 1 , si 1 es una posición N, entonces A gana , de lo contrario, B gana .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the winner
char Winner(int N)
{
    bool player = true;
 
    // Backtrack from N to 1
    while(N > 1)
    {
        int den = (player) ? 9 : 2;
        int X = N/den, Y = N%den;
        N = (Y)? X + 1: X;
        player = !player;
    }
    if (player)
      return 'B';
    else
      return 'A';
}
 
// Driver Code
int main()
{
  int N = 10;
  cout << Winner(N);
  return 0;
}
 
// This code is contributed by mohit kumar 29.

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to find the winner
  static char Winner(int N)
  {
    boolean player = true;
 
    // Backtrack from N to 1
    while(N > 1)
    {
      int den = (player) ? 9 : 2;
      int X = N / den;
      int Y = N % den;
      N = (Y > 0) ? X + 1: X;
      player = !player;
    }
    if (player)
      return 'B';
    else
      return 'A';
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 10;
    System.out.print(Winner(N));
  }
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to find the winner
def Winner(N):
    player = True
     
    # Backtrack from N to 1
    while N > 1:
                 
        X, Y = divmod(N, (9 if player else 2))
         
        N = X + 1 if Y else X
        player = not player
     
    if player:
      return 'B'
    else:
      return 'A'
 
# Driver Code
N = 10
print(Winner(N))

// C# program for the above approach
using System;
class GFG
{
 
  // Function to find the winner
  static char Winner(int N)
  {
      bool player = true;
 
      // Backtrack from N to 1
      while (N > 1)
      {
          int den = (player) ? 9 : 2;
          int X = N / den;
          int Y = N % den;
          N = (Y > 0) ? X + 1 : X;
          player = !player;
      }
      if (player)
          return 'B';
      else
          return 'A';
  }
 
  // Driver Code
  static public void Main()
  {
    int N = 10;
    Console.WriteLine(Winner(N));
  }
}
 
// This code is contributed by Dharanendra L V

<script>
// Javascript program for the above approach
function Winner(N)
{
    var player = Boolean(true);
 
    // Backtrack from N to 1
    while(N > 1)
    {
        var den = (player) ? 9 : 2;
        var X = parseInt(N/den), Y = parseInt(N%den);
        N = (Y)? X + 1: X;
        player = !player;
    }
    if (player)
      document.write( 'B');
    else
      document.write( 'A');
}
var N = 10;
Winner(N);
 
// This code is contributed by SoumikMondal
</script>

B

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)