Cantidad máxima de dinero que puede recolectar un jugador en un juego de monedas

Dada una array 2D Arr[][] que consta de N filas y dos personas A y B jugando un juego de turnos alternos basado en las siguientes reglas:

• Se elige una fila al azar, donde A solo puede tomar la moneda que queda más a la izquierda, mientras que B solo puede tomar la moneda que queda más a la derecha en la fila elegida.
• El juego termina cuando no quedan monedas.

La tarea es determinar la cantidad máxima de dinero obtenida por A .

 Ejemplos:

Entrada: N = 2, Arr[][] = {{ 5, 2, 3, 4 }, { 1, 6 }}
Salida: 8
Explicación: 
Fila 1: 5, 2, 3, 4
Fila 2: 1, 6
Operaciones:

1. A toma la moneda con valor 5
2. B toma la moneda con valor 4
3. A toma la moneda con valor 2
4. B toma la moneda con valor 3
5. A toma la moneda con valor 1
6. B toma la moneda con valor 6

Óptimamente, dinero recaudado por A = 5 + 2 + 1 = 8 
Dinero recaudado por B = 3 + 4 + 6 = 13

Entrada: N = 1, Arr[] = {{ 1, 2, 3 }}
Salida : 3

  Enfoque: siga los pasos a continuación para resolver el problema

1. En un juego jugado con una estrategia óptima
2. Inicialice una variable, digamos cantidad , para almacenar el dinero obtenido por A.
3. Si N es par, A recogerá la primera mitad de las monedas.
4. De lo contrario, primero, (N/2) monedas serían recolectadas por A y las últimas (N/2) serían recolectadas por B
5. Si N es impar, A o B pueden recoger la moneda del medio , dependiendo de la secuencia de movimientos.
6. Guarde la moneda en el medio de todas las filas de tamaño impar en una variable, digamos mid_odd[].
7. Ordene la array mid_odd[] en orden descendente.
8. Óptimamente, A recolectaría todas las monedas en índices pares de min_odd[]
9. Finalmente, imprima la puntuación de A .

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

// CPP Program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate the
// maximum amount collected by A
void find(int N,  vector<vector<int>>Arr)
{
     
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    vector<int> mid_odd;
    for(int i = 0; i < N; i++)
    {
 
        // Size of current row
        int siz = Arr[i].size();
 
        // Increase money collected by A
        for (int j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.push_back(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    sort(mid_odd.begin(),mid_odd.end());
 
    for(int i = 0; i < mid_odd.size(); i++)
        if (i % 2 == 0)
         amount = amount + mid_odd[i];
 
    // Print the amount
    cout<<amount<<endl;
 
}
 
// Driver Code
int main()
{
   int N = 2;
   vector<vector<int>>Arr{{5, 2, 3, 4}, {1, 6}};
 
   // Function call to calculate the
   // amount of coins collected by A
   find(N, Arr);
}
 
// This code is contributed by ipg2016107.

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
  
// Function to calculate the
// maximum amount collected by A
static void find(int N, int[][] Arr)
{
     
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    ArrayList<Integer> mid_odd
            = new ArrayList<Integer>();
    for(int i = 0; i < N; i++)
    {
 
        // Size of current row
        int siz = Arr[i].length;
 
        // Increase money collected by A
        for (int j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.add(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    Collections.sort(mid_odd);
     
    for(int i = 0; i < mid_odd.size(); i++){
        if (i % 2 == 0)
         amount = amount + mid_odd.get(i);
    }
 
    // Print the amount
    System.out.println(amount);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2;
   int[][] Arr = {{5, 2, 3, 4}, {1, 6}};
 
   // Function call to calculate the
   // amount of coins collected by A
   find(N, Arr);
}
}
  
// This code is contributed by splevel62.

# Python Program to implement
# the above approach
 
# Function to calculate the
# maximum amount collected by A
 
 
def find(N, Arr):
 
    # Stores the money
    # obtained by A
    amount = 0
 
    # Stores mid elements
    # of odd sized rows
    mid_odd = []
 
    for i in range(N):
 
        # Size of current row
        siz = len(Arr[i])
 
        # Increase money collected by A
        for j in range(0, siz // 2):
            amount = amount + Arr[i][j]
 
        if(siz % 2 == 1):
            mid_odd.append(Arr[i][siz // 2])
 
    # Add coins at even indices
    # to the amount collected by A
    mid_odd.sort(reverse=True)
 
    for i in range(len(mid_odd)):
        if i % 2 == 0:
            amount = amount + mid_odd[i]
 
    # Print the amount
    print(amount)
 
 
# Driver Code
 
N = 2
Arr = [[5, 2, 3, 4], [1, 6]]
 
# Function call to calculate the
# amount of coins collected by A
find(N, Arr)

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to calculate the
  // maximum amount collected by A
  static void find(int N, List<List<int>> Arr)
  {
 
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    List<int> mid_odd = new List<int>();
    for(int i = 0; i < N; i++)
    {
 
      // Size of current row
      int siz = Arr[i].Count;
 
      // Increase money collected by A
      for (int j = 0; j < siz / 2; j++)
        amount = amount + Arr[i][j];
 
      if(siz % 2 == 1)
        mid_odd.Add(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    mid_odd.Sort();
 
    for(int i = 0; i < mid_odd.Count; i++)
      if (i % 2 == 0)
        amount = amount + mid_odd[i];
 
    // Print the amount
    Console.WriteLine(amount);
 
  }
 
  // Driver code
  static void Main()
  {
    int N = 2;
    List<List<int>> Arr = new List<List<int>>();
    Arr.Add(new List<int>());
    Arr[0].Add(5);
    Arr[0].Add(2);
    Arr[0].Add(3);
    Arr[0].Add(4);
    Arr.Add(new List<int>());
    Arr[1].Add(1);
    Arr[1].Add(6);
 
    // Function call to calculate the
    // amount of coins collected by A
    find(N, Arr);
  }
}
 
// This code is contributed by divyesh072019.

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to calculate the
// maximum amount collected by A
function find(N,  Arr)
{
     
    // Stores the money
    // obtained by A
    var amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    var mid_odd = [];
    for(var i = 0; i < N; i++)
    {
 
        // Size of current row
        var siz = Arr[i].length;
 
        // Increase money collected by A
        for (var j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.push(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    mid_odd.sort((a,b)=>a-b)
 
    for(var i = 0; i < mid_odd.length; i++)
        if (i % 2 == 0)
         amount = amount + mid_odd[i];
 
    // Print the amount
    document.write( amount + "<br>");
 
}
 
// Driver Code
var N = 2;
var Arr = [[5, 2, 3, 4], [1, 6]];
 
// Function call to calculate the
// amount of coins collected by A
find(N, Arr);
 
// This code is contributed by importantly.
</script>

8

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)