Encuentre el ganador de un juego de quitar cualquier cantidad de piedras de la pila no vacía menos indexada de N pilas dadas

Dada una array arr[] que consta de N enteros, cada uno de los cuales representa el tamaño de una pila de piedras. La tarea es determinar el ganador del juego cuando dos jugadores, A y B , juegan un juego de manera óptima según las siguientes condiciones:

• El jugador A siempre comienza el juego.
• En un movimiento, un jugador puede quitar cualquier cantidad de piedras (al menos 1), de la primera pila no vacía con un índice mínimo.
• El primer jugador que no puede hacer un movimiento pierde el juego.

Imprime “ A” si el jugador A gana el juego. De lo contrario, imprima “ B” .

Ejemplos:

Entrada: arr[] = {1, 1, 1, 1, 1, 1}
Salida: B
Explicación:
Aquí, cada pila tiene solo una piedra, por lo que A y B alternativamente quitarán una piedra cada uno.
A saca 1 piedra del primer montón, B saca 1 del segundo montón y así sucesivamente.
B retira la última piedra del sexto montón.
Como A no tiene otra opción, B gana el juego.

Entrada: arr[] = {1, 1, 2, 1}
Salida: A
Explicación:
Aquí, 
A quita 1 piedra de la primera pila, 
B quita 1 de la segunda pila, 
A quita solo 1 de la tercera pila 
y ahora B está forzado para quitar 1 de la 3ra pila. 
A quita la última piedra de la cuarta pila.
Como a B no le queda otra opción, A gana el juego.

Enfoque: la idea es descubrir las formas óptimas que los jugadores deben seguir para ganar el juego. A continuación hay dos formas de jugar de manera óptima:

• Para todas las pilas excepto la última, si hay K piedras en una pila, el jugador actual elegirá solo ( K – 1 ) piedras (solo si K > 1) de modo que otro jugador se vea obligado a elegir la piedra restante. Esto garantiza que el jugador actual tenga la oportunidad de elegir piedras del siguiente montón y, finalmente, ganar.
• Para la última pila, si tiene K piedras, entonces el jugador actual recogerá todas las K piedras para que el otro jugador no tenga la oportunidad de recoger piedras. Esto eventualmente garantiza que el jugador actual gane.

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

1. Inicialmente, asumiendo que el jugador quitará todas las piedras de la pila actual, A será el ganador si el tamaño de la array es impar y B si el tamaño es par .
2. Ahora, itere sobre el rango [0, N – 2] y verifique el índice actual y la cantidad de piedras presentes en la pila actual para decidir qué jugador ganará.
3. Mientras atraviesa, si el índice es par, A tendrá la oportunidad de elegir una piedra. De lo contrario, B tendrá la oportunidad de recoger piedras.
4. Si el índice actual es par y el número de piedras es mayor que 1 , entonces el ganador se establece en B. Actualice el ganador a A .
5. Si el índice actual es impar y el número de piedras supera 1 , el ganador será A . Luego, actualice el ganador a B .
6. Finalmente, imprime el ganador del juego.

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
// of game between A and B
void findWinner(int a[], int n)
{
    // win = 1 means B is winner
    // win = 0 means A is winner
    int win = 0;
 
    // If size is even, winner is B
    if (n % 2 == 0)
        win = 1;
 
    // If size is odd, winner is A
    else
        win = 0;
 
    for (int i = n - 2; i >= 0; i--) {
 
        // Stone will be removed by B
        if (i % 2 == 1) {
 
            // If B wants to win
 
            // B will take n-1 stones
            // from current pile having
            // n stones and force A to
            // pick 1 stone
            if (win == 0 && a[i] > 1)
                win = 1;
        }
 
        // Stone will be removed by A
        else {
 
            // If A wants to win
 
            // A will take n-1 stones from
            // current pile having n stones
            // and force B to pick 1 stone
            if (win == 1 && a[i] > 1)
                win = 0;
        }
    }
 
    // Print the winner accordingly
    if (win == 0)
        cout << "A";
    else
        cout << "B";
}
 
// Driver Code
int main()
{
    // Given piles of stone
    int arr[] = { 1, 1, 1, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    findWinner(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the winner
// of game between A and B
static void findWinner(int a[], int n)
{
     
    // win = 1 means B is winner
    // win = 0 means A is winner
    int win = 0;
 
    // If size is even, winner is B
    if (n % 2 == 0)
        win = 1;
 
    // If size is odd, winner is A
    else
        win = 0;
 
    for(int i = n - 2; i >= 0; i--)
    {
         
        // Stone will be removed by B
        if (i % 2 == 1)
        {
             
            // If B wants to win
 
            // B will take n-1 stones
            // from current pile having
            // n stones and force A to
            // pick 1 stone
            if (win == 0 && a[i] > 1)
                win = 1;
        }
 
        // Stone will be removed by A
        else
        {
             
            // If A wants to win
 
            // A will take n-1 stones from
            // current pile having n stones
            // and force B to pick 1 stone
            if (win == 1 && a[i] > 1)
                win = 0;
        }
    }
 
    // Print the winner accordingly
    if (win == 0)
        System.out.print("A");
    else
        System.out.print("B");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given piles of stone
    int arr[] = { 1, 1, 1, 2 };
 
    int N = arr.length;
 
    // Function call
    findWinner(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to find the winner
# of game between A and B
def findWinner(a, n):
     
    # win = 1 means B is winner
    # win = 0 means A is winner
    win = 0
 
    # If size is even, winner is B
    if (n % 2 == 0):
        win = 1
 
    # If size is odd, winner is A
    else:
        win = 0
 
    for i in range(n - 2, -1, -1):
 
        # Stone will be removed by B
        if (i % 2 == 1):
 
            # If B wants to win
 
            # B will take n-1 stones
            # from current pile having
            # n stones and force A to
            # pick 1 stone
            if (win == 0 and a[i] > 1):
                win = 1
 
        # Stone will be removed by A
        else:
 
            # If A wants to win
 
            # A will take n-1 stones from
            # current pile having n stones
            # and force B to pick 1 stone
            if (win == 1 and a[i] > 1):
                win = 0
                 
    # Print the winner accordingly
    if (win == 0):
        print("A")
    else:
        print("B")
 
# Driver Code
if __name__ == '__main__':
     
    # Given piles of stone
    arr = [ 1, 1, 1, 2 ]
 
    N = len(arr)
 
    # Function call
    findWinner(arr, N)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
class GFG{
 
// Function to find the winner
// of game between A and B
static void findWinner(int []a,
                       int n)
{   
  // win = 1 means B is winner
  // win = 0 means A is winner
  int win = 0;
 
  // If size is even, winner is B
  if (n % 2 == 0)
    win = 1;
 
  // If size is odd, winner is A
  else
    win = 0;
 
  for(int i = n - 2; i >= 0; i--)
  {
    // Stone will be removed by B
    if (i % 2 == 1)
    {
 
      // If B wants to win
 
      // B will take n-1 stones
      // from current pile having
      // n stones and force A to
      // pick 1 stone
      if (win == 0 && a[i] > 1)
        win = 1;
    }
 
    // Stone will be removed by A
    else
    {
      // If A wants to win
      // A will take n-1 stones from
      // current pile having n stones
      // and force B to pick 1 stone
      if (win == 1 && a[i] > 1)
        win = 0;
    }
  }
 
  // Print the winner accordingly
  if (win == 0)
    Console.Write("A");
  else
    Console.Write("B");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given piles of stone
  int []arr = {1, 1, 1, 2};
 
  int N = arr.Length;
 
  // Function call
  findWinner(arr, N);
}
}
 
 // This code is contributed by Rajput-Ji

<script>
// Javascript program for the above approach
 
// Function to find the winner
// of game between A and B
function findWinner(a, n)
{
 
    // win = 1 means B is winner
    // win = 0 means A is winner
    let win = 0;
  
    // If size is even, winner is B
    if (n % 2 == 0)
        win = 1;
  
    // If size is odd, winner is A
    else
        win = 0;
  
    for(let i = n - 2; i >= 0; i--)
    {
          
        // Stone will be removed by B
        if (i % 2 == 1)
        {
              
            // If B wants to win
  
            // B will take n-1 stones
            // from current pile having
            // n stones and force A to
            // pick 1 stone
            if (win == 0 && a[i] > 1)
                win = 1;
        }
  
        // Stone will be removed by A
        else
        {
              
            // If A wants to win
  
            // A will take n-1 stones from
            // current pile having n stones
            // and force B to pick 1 stone
            if (win == 1 && a[i] > 1)
                win = 0;
        }
    }
  
    // Print the winner accordingly
    if (win == 0)
        document.write("A");
    else
        document.write("B");
}
 
// Driver Code
// Given piles of stone
let arr=[1, 1, 1, 2];
let N = arr.length;
 
// Function call
findWinner(arr, N);
 
// This code is contributed by unknown2108
</script>

B

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