Dada una array arr[] que consta de N enteros positivos, tal que arr[i] representa el valor de la moneda, la tarea es encontrar la cantidad máxima de dinero que puede obtener cada jugador cuando dos jugadores A y B juegan el juego de manera óptima según las siguientes reglas:
- El jugador A siempre comienza el juego.
- En cada turno, un jugador debe retirar exactamente 1 moneda de la array dada.
- En cada turno, el jugador B debe retirar exactamente 2 monedas de la array dada.
Ejemplos:
Entrada: arr[] = {1, 1, 1, 1}
Salida: (A : 2), (B : 2)
Explicación: Las
siguientes son las secuencias de monedas extraídas por ambos jugadores:
- El jugador A elimina arr[0](= 1).
- El jugador B elimina arr[1](= 1) y arr[2](= 1).
- El jugador A elimina arr[3](= 1).
Por lo tanto, el total de monedas obtenidas por el jugador A es 2 y el jugador B es 2.
Entrada: arr[] = {1, 1, 1}
Salida: (A : 1), (B : 2)
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Inicializa dos variables, digamos cantidadA y cantidadB como 0 que almacena la cantidad total de dinero obtenida por los jugadores A y B.
- Ordena la array dada en orden descendente .
- Si el valor de N es 1 , actualice el valor de cantidadA a arr[0] .
- Si el valor de N es mayor o igual a 2 , actualice el valor de cantidadA a arr[0] y el valor de cantidadB a arr[1] .
- Recorra la array arr[] sobre el rango [2, N] usando la variable i , y si el valor de i es par , agregue el valor arr[i] a la cantidadB . De lo contrario, agregue el valor arr[i] a la cantidadA .
- Después de completar los pasos anteriores, imprima el valor de la cantidad A y la cantidad B como el resultado de la puntuación de los jugadores A y B , respectivamente.
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
// obtained by the players A and B
void findAmountPlayers(int arr[], int N)
{
// Sort the array in descending order
sort(arr, arr + N, greater<int>());
// Stores the maximum amount of
// money obtained by A
int amountA = 0;
// Stores the maximum amount of
// money obtained by B
int amountB = 0;
// If the value of N is 1
if (N == 1) {
// Update the amountA
amountA += arr[0];
// Print the amount of money
// obtained by both players
cout << "(A : " << amountA << "), "
<< "(B : " << amountB << ")";
return;
}
// Update the amountA
amountA = arr[0];
// Update the amountB
amountB = arr[1];
// Traverse the array arr[]
for (int i = 2; i < N; i++) {
// If i is an odd number
if (i % 2 == 0) {
// Update the amountB
amountB += arr[i];
}
else {
// Update the amountA
amountA += arr[i];
}
}
// Print the amount of money
// obtained by both the players
cout << "(A : " << amountA << ")\n"
<< "(B : " << amountB << ")";
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
findAmountPlayers(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum score
// obtained by the players A and B
static void findAmountPlayers(int[] arr, int N)
{
// Sort the array in descending order
Arrays.sort(arr);
reverse(arr, N);
// Stores the maximum amount of
// money obtained by A
int amountA = 0;
// Stores the maximum amount of
// money obtained by B
int amountB = 0;
// If the value of N is 1
if (N == 1)
{
// Update the amountA
amountA += arr[0];
// Print the amount of money
// obtained by both players
System.out.println("(A : " + amountA + "), " +
"(B : " + amountB + ")");
return;
}
// Update the amountA
amountA = arr[0];
// Update the amountB
amountB = arr[1];
// Traverse the array arr[]
for(int i = 2; i < N; i++)
{
// If i is an odd number
if (i % 2 == 0)
{
// Update the amountB
amountB += arr[i];
}
else
{
// Update the amountA
amountA += arr[i];
}
}
// Print the amount of money
// obtained by both the players
System.out.println("(A : " + amountA + ")");
System.out.println("(B : " + amountB + ")");
}
static void reverse(int a[], int n)
{
int[] b = new int[n];
int j = n;
for(int i = 0; i < n; i++)
{
b[j - 1] = a[i];
j = j - 1;
}
}
// Driver code
public static void main(String []args)
{
int[] arr = { 1, 1, 1 };
int N = arr.length;
findAmountPlayers(arr, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
# Function to find the maximum score
# obtained by the players A and B
def findAmountPlayers(arr, N):
# Sort the array in descending order
arr = sorted(arr)[::-1]
# Stores the maximum amount of
# money obtained by A
amountA = 0
# Stores the maximum amount of
# money obtained by B
amountB = 0
# If the value of N is 1
if (N == 1):
# Update the amountA
amountA += arr[0]
# Print the amount of money
# obtained by both players
print("(A :",mountA,"), (B :",str(amountB)+")")
return
# Update the amountA
amountA = arr[0]
# Update the amountB
amountB = arr[1]
# Traverse the array arr[]
for i in range(2, N):
# If i is an odd number
if (i % 2 == 0):
# Update the amountB
amountB += arr[i]
else:
# Update the amountA
amountA += arr[i]
# Print amount of money
# obtained by both the players
print("(A :",str(amountA)+")\n(B :",str(amountB)+")")
# Driver Code
if __name__ == '__main__':
arr = [1, 1, 1]
N = len(arr)
findAmountPlayers(arr, N)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the maximum score
// obtained by the players A and B
static void findAmountPlayers(int[] arr, int N)
{
// Sort the array in descending order
Array.Sort(arr);
Array.Reverse(arr);
// Stores the maximum amount of
// money obtained by A
int amountA = 0;
// Stores the maximum amount of
// money obtained by B
int amountB = 0;
// If the value of N is 1
if (N == 1) {
// Update the amountA
amountA += arr[0];
// Print the amount of money
// obtained by both players
Console.WriteLine("(A : " + amountA + "), "
+ "(B : " + amountB + ")");
return;
}
// Update the amountA
amountA = arr[0];
// Update the amountB
amountB = arr[1];
// Traverse the array arr[]
for (int i = 2; i < N; i++) {
// If i is an odd number
if (i % 2 == 0) {
// Update the amountB
amountB += arr[i];
}
else {
// Update the amountA
amountA += arr[i];
}
}
// Print the amount of money
// obtained by both the players
Console.WriteLine("(A : " + amountA + ")");
Console.WriteLine("(B : " + amountB + ")");
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 1, 1 };
int N = arr.Length;
findAmountPlayers(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum score
// obtained by the players A and B
function findAmountPlayers(arr, N) {
// Sort the array in descending order
arr.sort((a, b) => b - a)
// Stores the maximum amount of
// money obtained by A
let amountA = 0;
// Stores the maximum amount of
// money obtained by B
let amountB = 0;
// If the value of N is 1
if (N == 1) {
// Update the amountA
amountA += arr[0];
// Print the amount of money
// obtained by both players
document.write("(A : " + amountA + "), "
+ "(B : " + amountB + ")");
return;
}
// Update the amountA
amountA = arr[0];
// Update the amountB
amountB = arr[1];
// Traverse the array arr[]
for (let i = 2; i < N; i++) {
// If i is an odd number
if (i % 2 == 0) {
// Update the amountB
amountB += arr[i];
}
else {
// Update the amountA
amountA += arr[i];
}
}
// Print the amount of money
// obtained by both the players
document.write("(A : " + amountA + ")<br>"
+ "(B : " + amountB + ")");
}
// Driver Code
let arr = [1, 1, 1];
let N = arr.length
findAmountPlayers(arr, N);
// This code is contributed _saurabh_jaiswal
</script>
Producción:
(A : 1) (B : 2)
Complejidad temporal: O(N)
Espacio auxiliar: O(1)