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:
- A toma la moneda con valor 5
- B toma la moneda con valor 4
- A toma la moneda con valor 2
- B toma la moneda con valor 3
- A toma la moneda con valor 1
- B toma la moneda con valor 6
Óptimamente, dinero recaudado por A = 5 + 2 + 1 = 8
Dinero recaudado por B = 3 + 4 + 6 = 13Entrada: N = 1, Arr[] = {{ 1, 2, 3 }}
Salida : 3
Enfoque: siga los pasos a continuación para resolver el problema
- En un juego jugado con una estrategia óptima
- Inicialice una variable, digamos cantidad , para almacenar el dinero obtenido por A.
- Si N es par, A recogerá la primera mitad de las monedas.
- De lo contrario, primero, (N/2) monedas serían recolectadas por A y las últimas (N/2) serían recolectadas por B
- Si N es impar, A o B pueden recoger la moneda del medio , dependiendo de la secuencia de movimientos.
- Guarde la moneda en el medio de todas las filas de tamaño impar en una variable, digamos mid_odd[].
- Ordene la array mid_odd[] en orden descendente.
- Óptimamente, A recolectaría todas las monedas en índices pares de min_odd[]
- Finalmente, imprima la puntuación de A .
A continuación se muestra la implementación del enfoque anterior:
C++
// 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
// 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.
Python3
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por vermashivani543 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA