Dado un entero positivo N , que representa el recuento de jugadores que juegan el juego y una array de strings arr[] , que consta de strings numéricas formadas por dígitos del rango [‘1’, ‘N’] . Teniendo en cuenta que al i -ésimo jugador se le asigna la string arr[i] , la tarea es encontrar el ganador del juego cuando todos los N jugadores juegan el juego de manera óptima según las siguientes reglas:
- El jugador 1 comienza el juego, elimina el primer carácter de la string arr[1] ( indexación basada en 1 ), digamos X , y en el siguiente turno , el jugador X jugará el juego y eliminará el primer carácter de arr[X] y pronto.
- El jugador que no pueda eliminar ningún carácter de la string asignada ganará el juego.
Ejemplos:
Entrada: N = 3, arr[] = { “323”, “2”, “2” }
Salida: Jugador 2
Explicación:
Turno 1: Eliminar arr[0][0] por parte del Jugador 1 modifica arr[0] a “ 23”.
Turno 2: Eliminar arr[2][0] por parte del jugador 3 modifica arr[2] a “”.
Turno 3: Eliminar arr[1][0] por parte del jugador 2 modifica arr[1] a “”.
Turno 4: el jugador 2 no puede eliminar ningún personaje de arr[1].
Por lo tanto, el jugador 2 gana el juego.Entrada: N = 3, arr[] = { “121”, “21”, “23123” }
Salida: Jugador 1
Enfoque: el problema se puede resolver utilizando Queue para eliminar el primer carácter de cada string de manera eficiente. Siga los pasos a continuación para resolver el problema:
- Inicialice una array de Queues , digamos Q[] , de modo que Q[i] almacene los caracteres de la string arr[i] .
- Recorra la array Q[] usando la variable i según las reglas del juego y verifique si el conteo de caracteres en Q[i] es 0 o no. Si se determina que es cierto, imprima el «Jugador i» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the winner of a game of
// repeatedly removing the first character
// to empty a string
void find_Winner(vector<string>& arr, int N)
{
// Store characters of each
// string of the array arr[]
vector<queue<char> > Q(N);
// Stores count of strings in arr[]
int M = arr.size();
// Traverse the array arr[]
for (int i = 0; i < M; i++) {
// Stores length of current string
int len = arr[i].length();
// Traverse the string
for (int j = 0; j < len; j++) {
// Insert arr[i][j]
Q[i].push(arr[i][j] - 1);
}
}
// 1st Player starts the game
int player = 0;
while (Q[player].size() > 0) {
// Stores the player number
// for the next turn
int nextPlayer
= Q[player].front() - '0';
// Remove 1st character of
// current string
Q[player].pop();
// Update player number for
// the next turn
player = nextPlayer;
}
cout << "Player " << (player + 1);
}
// Driver Code
int main()
{
int N = 3;
vector<string> arr
= { "323", "2", "2" };
find_Winner(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the winner of a game of
// repeatedly removing the first character
// to empty a String
static void find_Winner(String[] arr, int N)
{
// Store characters of each
// String of the array arr[]
@SuppressWarnings("unchecked")
Vector<Character> [] Q = new Vector[N];
for (int i = 0; i < Q.length; i++)
Q[i] = new Vector<Character>();
// Stores count of Strings in arr[]
int M = arr.length;
// Traverse the array arr[]
for (int i = 0; i < M; i++)
{
// Stores length of current String
int len = arr[i].length();
// Traverse the String
for (int j = 0; j < len; j++)
{
// Insert arr[i][j]
Q[i].add(arr[i].charAt(j));
}
}
// 1st Player starts the game
int player = 0;
while (Q[player].size() > 0 )
{
// Stores the player number
// for the next turn
int nextPlayer
= Q[player].get(0) - '0'-1;
// Remove 1st character of
// current String
Q[player].remove(0);
// Update player number for
// the next turn
player = nextPlayer;
}
System.out.print("Player " + (player + 1));
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
String[] arr
= { "323", "2", "2" };
find_Winner(arr, N);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement
# the above approach
# Function to find the winner of a game of
# repeatedly removing the first character
# to empty a string
def find_Winner(arr, N) :
# Store characters of each
# string of the array arr[]
Q = [0]*N
for i in range(N) :
Q[i] = []
# Stores count of strings in arr[]
M = len(arr)
# Traverse the array arr[]
for i in range(M) :
# Stores length of current string
Len = len(arr[i])
# Traverse the string
for j in range(Len) :
# Insert arr[i][j]
Q[i].append(ord(arr[i][j]) - 1)
# 1st Player starts the game
player = 0
while (len(Q[player]) > 0) :
# Stores the player number
# for the next turn
nextPlayer = Q[player][0] - ord('0')
# Remove 1st character of
# current string
del Q[player][0]
# Update player number for
# the next turn
player = nextPlayer
print("Player", (player + 1))
N = 3
arr = [ "323", "2", "2" ]
find_Winner(arr, N)
# This code is contributed by divyeshrabadiya07.
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the winner of a game of
// repeatedly removing the first character
// to empty a String
static void find_Winner(String[] arr, int N)
{
// Store characters of each
// String of the array []arr
List<char> [] Q = new List<char>[N];
for(int i = 0; i < Q.Length; i++)
Q[i] = new List<char>();
// Stores count of Strings in []arr
int M = arr.Length;
// Traverse the array []arr
for(int i = 0; i < M; i++)
{
// Stores length of current String
int len = arr[i].Length;
// Traverse the String
for(int j = 0; j < len; j++)
{
// Insert arr[i,j]
Q[i].Add(arr[i][j]);
}
}
// 1st Player starts the game
int player = 0;
while (Q[player].Count > 0 )
{
// Stores the player number
// for the next turn
int nextPlayer = Q[player][0] - '0'- 1;
// Remove 1st character of
// current String
Q[player].RemoveAt(0);
// Update player number for
// the next turn
player = nextPlayer;
}
Console.Write("Player " + (player + 1));
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
String[] arr = { "323", "2", "2" };
find_Winner(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the winner of a game of
// repeatedly removing the first character
// to empty a string
function find_Winner( arr, N)
{
// Store characters of each
// string of the array arr[]
var Q = Array.from(Array(N), ()=>Array())
// Stores count of strings in arr[]
var M = arr.length;
// Traverse the array arr[]
for (var i = 0; i < M; i++) {
// Stores length of current string
var len = arr[i].length;
// Traverse the string
for (var j = 0; j < len; j++) {
// Insert arr[i][j]
Q[i].push(arr[i][j] - 1);
}
}
// 1st Player starts the game
var player = 0;
while (Q[player].length > 0) {
// Stores the player number
// for the next turn
var nextPlayer
= Q[player][0] - '0';
// Remove 1st character of
// current string
Q[player].shift();
// Update player number for
// the next turn
player = nextPlayer;
}
document.write( "Player " + (player + 1));
}
// Driver Code
var N = 3;
var arr
= ["323", "2", "2"];
find_Winner(arr, N);
// This code is contributed by rutvik_56.
</script>
Producción:
Player 2
Complejidad de tiempo: O(N * M), donde M es la longitud de la string más larga presente en la array.
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA