Considere un juego de monedas de dos jugadores donde cada jugador obtiene su turno uno por uno. Hay una fila de un número par de monedas, y un jugador en su turno puede sacar una moneda de cualquiera de las dos esquinas de la fila. El jugador que recoge monedas con más valor gana el juego. Desarrolle una estrategia para el jugador que realiza el primer turno, de modo que nunca pierda el juego.
Tenga en cuenta que la estrategia para seleccionar un máximo de dos esquinas puede no funcionar. En el siguiente ejemplo, el primer jugador pierde el juego cuando usa la estrategia para elegir un máximo de dos esquinas.
Ejemplo:
18 20 15 30 10 14 First Player picks 18, now row of coins is 20 15 30 10 14 Second player picks 20, now row of coins is 15 30 10 14 First Player picks 15, now row of coins is 30 10 14 Second player picks 30, now row of coins is 10 14 First Player picks 14, now row of coins is 10 Second player picks 10, game over. The total value collected by second player is more (20 + 30 + 10) compared to first player (18 + 15 + 14). So the second player wins.
Tenga en cuenta que este problema es diferente de Estrategia óptima para un juego | DP-31 . Allí el objetivo es obtener el máximo valor. Aquí el objetivo es no perder. Tenemos una estrategia codiciosa aquí. La idea es contar la suma de los valores de todas las monedas pares e impares, comparar los dos valores. El jugador que hace el primer movimiento siempre puede asegurarse de que el otro jugador nunca pueda elegir una moneda par si la suma de las monedas pares es mayor. Del mismo modo, puede asegurarse de que el otro jugador nunca pueda elegir una moneda impar si la suma de monedas impares es mayor.
Ejemplo:
18 20 15 30 10 14 Sum of odd coins = 18 + 15 + 10 = 43 Sum of even coins = 20 + 30 + 14 = 64. Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked the other player, the first player again gets an opportunity to pick an even coin and block all even coins.
C++
// CPP program to find coins to be picked to make sure
// that we never loose.
#include <iostream>
using namespace std;
// Returns optimal value possible that a player can collect
// from an array of coins of size n. Note than n must be even
void printCoins(int arr[], int n)
{
// Find sum of odd positioned coins
int oddSum = 0;
for (int i = 0; i < n; i += 2)
oddSum += arr[i];
// Find sum of even positioned coins
int evenSum = 0;
for (int i = 1; i < n; i += 2)
evenSum += arr[i];
// Print even or odd coins depending upon
// which sum is greater.
int start = ((oddSum > evenSum) ? 0 : 1);
for (int i = start; i < n; i += 2)
cout << arr[i] << " ";
}
// Driver program to test above function
int main()
{
int arr1[] = { 8, 15, 3, 7 };
int n = sizeof(arr1) / sizeof(arr1[0]);
printCoins(arr1, n);
cout << endl;
int arr2[] = { 2, 2, 2, 2 };
n = sizeof(arr2) / sizeof(arr2[0]);
printCoins(arr2, n);
cout << endl;
int arr3[] = { 20, 30, 2, 2, 2, 10 };
n = sizeof(arr3) / sizeof(arr3[0]);
printCoins(arr3, n);
return 0;
}
Java
// Java program to find coins to be
// picked to make sure that we never loose.
class GFG
{
// Returns optimal value possible
// that a player can collect from
// an array of coins of size n.
// Note than n must be even
static void printCoins(int arr[], int n)
{
// Find sum of odd positioned coins
int oddSum = 0;
for (int i = 0; i < n; i += 2)
oddSum += arr[i];
// Find sum of even positioned coins
int evenSum = 0;
for (int i = 1; i < n; i += 2)
evenSum += arr[i];
// Print even or odd coins depending
// upon which sum is greater.
int start = ((oddSum > evenSum) ? 0 : 1);
for (int i = start; i < n; i += 2)
System.out.print(arr[i]+" ");
}
// Driver Code
public static void main(String[] args)
{
int arr1[] = { 8, 15, 3, 7 };
int n = arr1.length;
printCoins(arr1, n);
System.out.println();
int arr2[] = { 2, 2, 2, 2 };
n = arr2.length;
printCoins(arr2, n);
System.out.println();
int arr3[] = { 20, 30, 2, 2, 2, 10 };
n = arr3.length;
printCoins(arr3, n);
}
}
// This code is contributed by ChitraNayal
Python3
# Python3 program to find coins # to be picked to make sure that # we never loose # Returns optimal value possible # that a player can collect from # an array of coins of size n. # Note than n must be even def printCoins(arr, n) : oddSum = 0 # Find sum of odd positioned coins for i in range(0, n, 2) : oddSum += arr[i] evenSum = 0 # Find sum of even # positioned coins for i in range(1, n, 2) : evenSum += arr[i] # Print even or odd # coins depending upon # which sum is greater. if oddSum > evenSum : start = 0 else : start = 1 for i in range(start, n, 2) : print(arr[i], end = " ") # Driver code if __name__ == "__main__" : arr1 = [8, 15, 3, 7] n = len(arr1) printCoins(arr1, n) print() arr2 = [2, 2, 2, 2] n = len(arr2) printCoins(arr2, n) print() arr3 = [20, 30, 2, 2, 2, 10] n = len(arr3) printCoins(arr3, n) # This code is contributed by ANKITRAI1
C#
// C# program to find coins to be
// picked to make sure that we never loose.
using System;
class GFG
{
// Returns optimal value possible
// that a player can collect from
// an array of coins of size n.
// Note than n must be even
static void printCoins(int[] arr, int n)
{
// Find sum of odd positioned coins
int oddSum = 0;
for (int i = 0; i < n; i += 2)
oddSum += arr[i];
// Find sum of even positioned coins
int evenSum = 0;
for (int i = 1; i < n; i += 2)
evenSum += arr[i];
// Print even or odd coins depending
// upon which sum is greater.
int start = ((oddSum > evenSum) ? 0 : 1);
for (int i = start; i < n; i += 2)
Console.Write(arr[i]+" ");
}
// Driver Code
public static void Main()
{
int[] arr1 = { 8, 15, 3, 7 };
int n = arr1.Length;
printCoins(arr1, n);
Console.Write("\n");
int[] arr2 = { 2, 2, 2, 2 };
n = arr2.Length;
printCoins(arr2, n);
Console.Write("\n");
int[] arr3 = { 20, 30, 2, 2, 2, 10 };
n = arr3.Length;
printCoins(arr3, n);
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP program to find coins to be
// picked to make sure that we never loose.
// Returns optimal value possible
// that a player can collect from
// an array of coins of size n.
// Note than n must be even
function printCoins(&$arr, $n)
{
// Find sum of odd positioned coins
$oddSum = 0;
for ($i = 0; $i < $n; $i += 2)
$oddSum += $arr[$i];
// Find sum of even positioned coins
$evenSum = 0;
for ($i = 1; $i < $n; $i += 2)
$evenSum += $arr[$i];
// Print even or odd coins depending
// upon which sum is greater.
$start = (($oddSum > $evenSum) ? 0 : 1);
for ($i = $start; $i < $n; $i += 2)
echo $arr[$i]." ";
}
// Driver Code
$arr1 = array( 8, 15, 3, 7 );
$n = sizeof($arr1);
printCoins($arr1, $n);
echo "\n";
$arr2 = array( 2, 2, 2, 2 );
$n = sizeof($arr2);
printCoins($arr2, $n);
echo "\n";
$arr3 = array( 20, 30, 2, 2, 2, 10 );
$n = sizeof($arr3);
printCoins($arr3, $n);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript program to find coins to
// be picked to make sure that we never
// loose.
// Returns optimal value possible that
// a player can collect from an array
// of coins of size n. Note than n must be even
function printCoins(arr, n)
{
// Find sum of odd positioned coins
var oddSum = 0;
for(var i = 0; i < n; i += 2)
oddSum += arr[i];
// Find sum of even positioned coins
var evenSum = 0;
for(var i = 1; i < n; i += 2)
evenSum += arr[i];
// Print even or odd coins depending upon
// which sum is greater.
var start = ((oddSum > evenSum) ? 0 : 1);
for(var i = start; i < n; i += 2)
document.write(arr[i] + " ");
}
// Driver code
var arr1 = [ 8, 15, 3, 7 ]
var n = arr1.length;
printCoins(arr1, n);
document.write("<br>");
var arr2 = [ 2, 2, 2, 2 ]
var n = arr2.length;
printCoins(arr2, n);
document.write("<br>");
var arr3 = [ 20, 30, 2, 2, 2, 10 ]
n = arr3.length;
printCoins(arr3, n);
// This code is contributed by noob2000
</script>
Producción:
15 7 2 2 30 2 10