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