Encuentra al ganador de un juego de quitar como máximo 3 piedras de una pila en cada turno

Dada una array arr[] de tamaño N , que denota valores asignados a N piedras, dos jugadores, Player1 y Player2 , juegan un juego de turnos alternos. En cada turno, un jugador puede tomar 1, 2 o 3 piedras de las primeras piedras restantes y la suma de los valores de todas las piedras eliminadas se suma a la puntuación del jugador. Teniendo en cuenta que ambos jugadores juegan de manera óptima, la tarea es imprimir el ganador del juego. Si ambos jugadores terminan el juego con la misma puntuación, imprime «Empate» .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 7}
Salida: Player2
Explicación: Player1 siempre perderá en un escenario óptimo.

Entrada: arr[] = {1, 2, 3, -9}
Salida: Jugador 1
Explicación: El Jugador 1 debe elegir las tres pilas en el primer movimiento para ganar y dejar al Jugador 2 con una puntuación negativa.
Si el jugador 1 elige solo una piedra, su puntaje será 1 y en el siguiente movimiento, el puntaje del jugador 2 se convertirá en 5. 
En el siguiente movimiento, el jugador 1 tomará la piedra con valor = -9 y perderá.
Si el jugador 1 elige dos montones, su puntaje será 3 y en el siguiente movimiento, el puntaje del jugador 2 será 3. 
En el siguiente movimiento, el jugador 1 tomará la piedra con valor = -9 y también perderá.

Enfoque ingenuo: el enfoque simple es elegir el número de piedras que maximizará la suma total de los valores de las piedras. Como ambos jugadores juegan de manera óptima y el Jugador 1 comienza el juego, el Jugador 1 elige 1, 2 o 3 piedras y las piedras restantes se pasan al siguiente jugador. Por lo tanto, la puntuación del Jugador2 debe restarse de la puntuación del Jugador1. La idea es utilizar la recursividad para resolver el problema. Sea res la puntuación máxima de Player1 que se obtiene después de las llamadas recursivas.

  • Si el resultado, res > 0 , Player1 gana
  • Si el resultado, res < 0 , Player2 gana
  • Si el resultado, res == 0 , entonces es un empate.

El árbol recursivo se ve así, donde algunos subproblemas se repiten muchas veces.

Siga los pasos para resolver el problema:

  • Declare una función recursiva , digamos maxScore(i) , para calcular la puntuación máxima de Player1 si el juego comienza en el índice i
    • Si el valor de i ≥ n , devuelve 0 .
    • Inicialice una variable, digamos puntuación como INT_MIN , para almacenar la puntuación máxima del jugador 1
      • Elige 1 piedra: puntuación = max(puntuación, arr[i] – maxScore(i + 1))
      • Elige 2 piedras, es decir (i + 1 < N) : puntuación = max(puntuación, arr[i] + arr[i + 1] – maxScore(i + 2))
      • Elige 3 piedras, es decir (i + 2 < N) : puntuación = max(puntuación, arr[i] + arr[i + 1] + arr[i + 2] – maxScore(i + 3))
    • Devuelve el valor de score .
  • Almacene el valor de maxScore(0) en una variable res .
  • Si el valor de res>0 , imprime “Jugador1” , si res<0 , imprime “Jugador2” , de lo contrario, imprime “Empate” .

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum score of Player1
int maximumStonesUtil(int* arr, int n, int i)
{
    // Base Case
    if (i >= n)
        return 0;
 
    // Variable to store maximum score
    int ans = INT_MIN;
 
    // Pick one stone
    ans = max(ans,
              arr[i] - maximumStonesUtil(arr, n, i + 1));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = max(ans,
                  arr[i] + arr[i + 1]
                      - maximumStonesUtil(arr, n, i + 2));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = max(ans,
                  arr[i] + arr[i + 1] + arr[i + 2]
                      - maximumStonesUtil(arr, n, i + 3));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
string maximumStones(int* arr, int n)
{
    // Store the result
    int res = maximumStonesUtil(arr, n, 0);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 1, 2, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << maximumStones(arr, n);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Function to find the maximum score of Player1
static int maximumStonesUtil(int[] arr, int n,
                             int i)
{
     
    // Base Case
    if (i >= n)
        return 0;
 
    // Variable to store maximum score
    int ans = Integer.MIN_VALUE;
 
    // Pick one stone
    ans = Math.max(ans, arr[i] - maximumStonesUtil(
                     arr, n, i + 1));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = Math.max(ans, arr[i] + arr[i + 1] -
               maximumStonesUtil(arr, n, i + 2));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = Math.max(
            ans,
            arr[i] + arr[i + 1] + arr[i + 2]
                - maximumStonesUtil(arr, n, i + 3));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
static String maximumStones(int[] arr, int n)
{
     
    // Store the result
    int res = maximumStonesUtil(arr, n, 0);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 7 };
    int n = arr.length;
 
    // Function Call
    System.out.println(maximumStones(arr, n));
}
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
import sys
 
# Function to find the maximum score of Player1
def maximumStonesUtil(arr, n, i):
     
    # Base Case
    if (i >= n):
        return 0
 
    # Variable to store maximum score
    ans = -sys.maxsize-1;
 
    # Pick one stone
    ans = max(
        ans, arr[i] - maximumStonesUtil(
                       arr, n, i + 1))
 
    # Pick 2 stones
    if (i + 1 < n):
        ans = max(
            ans, arr[i] + arr[i + 1]- maximumStonesUtil(
                      arr, n, i + 2))
 
    # Pick 3 stones
    if (i + 2 < n):
        ans = max(
            ans, arr[i] + arr[i + 1] + arr[i + 2]-
                 maximumStonesUtil(arr, n, i + 3));
 
    # Return the score of the player
    return ans
 
# Function to find the winner of the game
def maximumStones(arr, n):
     
    # Store the result
    res = maximumStonesUtil(arr, n, 0)
 
    # Player 1 wins
    if (res > 0):
        return "Player1"
 
    # PLayer 2 wins
    elif(res < 0):
        return "Player2"
 
    # Tie
    else:
        return "Tie"
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    arr = [ 1, 2, 3, 7 ]
    n = len(arr)
 
    # Function Call
    print(maximumStones(arr, n))
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program for the above approach
using System;
         
class GFG
{
 
// Function to find the maximum score of Player1
static int maximumStonesUtil(int[] arr, int n,
                             int i)
{
     
    // Base Case
    if (i >= n)
        return 0;
 
    // Variable to store maximum score
    int ans = Int32.MinValue;
 
    // Pick one stone
    ans = Math.Max(ans, arr[i] - maximumStonesUtil(
                     arr, n, i + 1));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = Math.Max(ans, arr[i] + arr[i + 1] -
               maximumStonesUtil(arr, n, i + 2));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = Math.Max(
            ans,
            arr[i] + arr[i + 1] + arr[i + 2]
                - maximumStonesUtil(arr, n, i + 3));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
static String maximumStones(int[] arr, int n)
{
     
    // Store the result
    int res = maximumStonesUtil(arr, n, 0);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
     
// Driver Code
public static void Main()
{
    int[] arr = { 1, 2, 3, 7 };
    int n = arr.Length;
 
    // Function Call
    Console.WriteLine(maximumStones(arr, n));
 
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
    // Javascript program for the above approach
     
    // Function to find the maximum score of Player1
    function maximumStonesUtil(arr, n, i)
    {
 
        // Base Case
        if (i >= n)
            return 0;
 
        // Variable to store maximum score
        let ans = Number.MIN_VALUE;
 
        // Pick one stone
        ans = Math.max(ans, arr[i] - maximumStonesUtil(arr, n, i + 1));
 
        // Pick 2 stones
        if (i + 1 < n)
            ans = Math.max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2));
 
        // Pick 3 stones
        if (i + 2 < n)
            ans = Math.max(
                ans,
                arr[i] + arr[i + 1] + arr[i + 2]
                    - maximumStonesUtil(arr, n, i + 3));
 
        // Return the score of the player
        return ans;
    }
 
    // Function to find the winner of the game
    function maximumStones(arr, n)
    {
 
        // Store the result
        let res = maximumStonesUtil(arr, n, 0);
 
        // Player 1 wins
        if (res < 0)
            return "Player1";
 
        // PLayer 2 wins
        else if (res > 0)
            return "Player2";
 
        // Tie
        else
            return "Tie";
    }
     
    let arr = [ 1, 2, 3, 7 ];
    let n = arr.length;
  
    // Function Call
    document.write(maximumStones(arr, n));
 
// This code is contributed by rameshtravel07.
</script>
Producción: 

Player2

 

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

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar programación dinámica . El problema dado tiene una propiedad de subestructura óptima y subproblemas superpuestos . Use la memorización creando una tabla 1D, dp de tamaño N para almacenar los resultados de las llamadas recursivas. 

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum score of Player 1
int maximumStonesUtil(int* arr, int n, int i,
                      vector<int>& dp)
{
    // Base Case
    if (i >= n)
        return 0;
 
    int& ans = dp[i];
 
    // If the result is already computed, then
    // return the result
    if (ans != -1)
        return ans;
 
    // Variable to store maximum score
    ans = INT_MIN;
 
    // Pick one stone
    ans = max(
        ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = max(ans, arr[i] + arr[i + 1]
                           - maximumStonesUtil(arr, n,
                                               i + 2, dp));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2]
                           - maximumStonesUtil(arr, n,
                                               i + 3, dp));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
string maximumStones(int* arr, int n)
{
    // Create a 1D table, dp of size N
    vector<int> dp(n, -1);
 
    // Store the result
    int res = maximumStonesUtil(arr, n, 0, dp);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 1, 2, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << maximumStones(arr, n);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
    static int ans = 0;
   
// Function to find the maximum score of Player 1
static int maximumStonesUtil(int[] arr, int n, int i,
                      int[] dp)
{
    // Base Case
    if (i >= n)
        return 0;
 
    ans = dp[i];
 
    // If the result is already computed, then
    // return the result
    if (ans != -1)
        return ans;
 
    // Variable to store maximum score
    ans = Integer.MIN_VALUE;
 
    // Pick one stone
    ans = Math.max(
        ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = Math.max(ans, arr[i] + arr[i + 1]
                           - maximumStonesUtil(arr, n,
                                               i + 2, dp));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = Math.max(ans, arr[i] + arr[i + 1] + arr[i + 2]
                           - maximumStonesUtil(arr, n,
                                               i + 3, dp));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
static String maximumStones(int []arr, int n)
{
    // Create a 1D table, dp of size N
    int []dp = new int[n];
    Arrays.fill(dp, -1);
 
    // Store the result
    int res = maximumStonesUtil(arr, n, 0, dp);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Input
    int arr[] = { 1, 2, 3, 7 };
    int n = arr.length;
 
    // Function Call
    System.out.print(maximumStones(arr, n));
 
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python program for the above approach
 
# Function to find the maximum score of Player 1
def maximumStonesUtil(arr, n, i, dp):
   
    # Base Case
    if (i >= n):
        return 0
     
    ans = dp[i]
     
    # If the result is already computed, then
    # return the result
    if (ans != -1):
        return ans
         
    # Variable to store maximum score
    ans = -2**31
     
    # Pick one stone
    ans = max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp))
     
    # Pick 2 stones
    if (i + 1 < n):
        ans = max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp))
         
    # Pick 3 stones
    if (i + 2 < n):
        ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp))
     
    # Return the score of the player
    return ans
 
 
# Function to find the winner of the game
def maximumStones(arr, n):
    # Create a 1D table, dp of size N
    dp =[-1]*n
     
    # Store the result
    res = maximumStonesUtil(arr, n, 0, dp)
     
    # Player 1 wins
    if (res > 0):
        return "Player1"
         
    # PLayer 2 wins
    elif (res < 0):
        return "Player2"
         
    # Tie
    else:
        return "Tie"
 
# Driver Code
 
# Given Input
arr = [1, 2, 3, 7]
n = len(arr)
 
# Function Call
print(maximumStones(arr, n))
 
# This code is contributed by shivani

C#

// C# program for the above approach
using System;
 
public class GFG
{
    static int ans = 0;
   
// Function to find the maximum score of Player 1
static int maximumStonesUtil(int[] arr, int n, int i,
                      int[] dp)
{
    // Base Case
    if (i >= n)
        return 0;
 
    ans = dp[i];
 
    // If the result is already computed, then
    // return the result
    if (ans != -1)
        return ans;
 
    // Variable to store maximum score
    ans = int.MinValue;
 
    // Pick one stone
    ans = Math.Max(
        ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = Math.Max(ans, arr[i] + arr[i + 1]
                           - maximumStonesUtil(arr, n,
                                               i + 2, dp));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = Math.Max(ans, arr[i] + arr[i + 1] + arr[i + 2]
                           - maximumStonesUtil(arr, n,
                                               i + 3, dp));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
static String maximumStones(int []arr, int n)
{
    // Create a 1D table, dp of size N
    int []dp = new int[n];
    for(int i = 0; i < n; i++)
        dp[i]=-1;
 
    // Store the result
    int res = maximumStonesUtil(arr, n, 0, dp);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given Input
    int []arr = { 1, 2, 3, 7 };
    int n = arr.Length;
 
    // Function Call
    Console.Write(maximumStones(arr, n));
 
}
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
// Javascript program for the above approach
let ans = 0 ;
 
  // Function to find the maximum score of Player 1
function maximumStonesUtil( arr, n,  i,
                       dp)
{
    // Base Case
    if (i >= n)
        return 0;
 
    ans = dp[i];
 
    // If the result is already computed, then
    // return the result
    if (ans != -1)
        return ans;
 
    // Variable to store maximum score
    ans = -Math.pow(2,31);
 
    // Pick one stone
    ans = Math.max(
        ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp));
 
    // Pick 2 stones
    if (i + 1 < n)
        ans = Math.max(ans, arr[i] + arr[i + 1]
                           - maximumStonesUtil(arr, n,
                                               i + 2, dp));
 
    // Pick 3 stones
    if (i + 2 < n)
        ans = Math.max(ans, arr[i] + arr[i + 1] + arr[i + 2]
                           - maximumStonesUtil(arr, n,
                                               i + 3, dp));
 
    // Return the score of the player
    return ans;
}
 
// Function to find the winner of the game
function maximumStones(arr, n)
{
    // Create a 1D table, dp of size N
    let dp = new Array(n).fill(-1);
    
    // Store the result
    let res = maximumStonesUtil(arr, n, 0, dp);
 
    // Player 1 wins
    if (res > 0)
        return "Player1";
 
    // PLayer 2 wins
    else if (res < 0)
        return "Player2";
 
    // Tie
    else
        return "Tie";
}
 
    // Driver Code
    let arr= [ 1, 2, 3, 7 ];
    let n = arr.length;
     
    // Function Call
    document.write(maximumStones(arr, n));
 
// This code is contributed by jana_sayantan.
<script>
Producción: 

Player2

 

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

Publicación traducida automáticamente

Artículo escrito por srinivasteja18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *