Dada una string binaria S , la tarea es determinar el ganador del juego cuando dos jugadores juegan un juego de manera óptima en turnos alternos con la string dada, según las siguientes condiciones:
- El jugador 1 siempre comienza primero.
- En cada turno, un jugador elimina una substring no vacía de la string dada.
- Después de que se vacíe la string dada, el jugador que tenga la cuenta mínima de 0 s ganará el juego. Si ambos jugadores tienen la misma cuenta de 0 s, imprima » Empate «.
Ejemplos:
Entrada: S = “00011”
Salida: Jugador 1
Explicación: Las substrings se pueden elegir de la siguiente manera:
Turno 1: El jugador 1 elimina la substring S[4…5]. Por lo tanto, el jugador 1 contiene «11».
Turno 2: el jugador 2 elimina la substring S[0…0]. Por lo tanto, el jugador 2 contiene «0».
Turno 3: el jugador 1 elimina la substring S[0…0]. Por lo tanto, el jugador 1 contiene «110».
Turno 4: el jugador 2 elimina la substring S[0…0]. Por lo tanto, el jugador 2 contiene «00».
Por lo tanto, el jugador 1 gana el juego.Entrada: S = “0110011”
Salida: Jugador 2
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- Si la cuenta de 0 s en la string es un número par , entonces el jugador 1 y el jugador 2 eligen la substring «0» en cada turno y ningún jugador ganará este juego.
- De lo contrario, almacene el conteo de 1 s consecutivos en una array y aplique la regla del juego de nim en la array.
- Nim-Sum: El valor XOR acumulativo del número de monedas/piedras en cada pila/montón (aquí 1s consecutivos) en cualquier punto del juego se llama Nim-Sum en ese punto.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntZero , para almacenar el conteo de 0 s en la string.
- Inicialice una variable, digamos cntConOne , para almacenar el recuento de 1 s consecutivos en la string.
- Inicialice una variable, digamos nimSum , para almacenar el Nim-Sum de 1 s consecutivos de la string dada.
- Recorra la array y calcule la cuenta de 0 s y nimSum .
- Finalmente, verifique si el valor de cntZero es un número par o no . Si se encuentra que es cierto, imprima Tie .
- De lo contrario, compruebe si el valor de nimSum es mayor que 0 o no. Si se encuentra que es cierto, imprima Player 1 .
- De lo contrario, imprima el reproductor 2 .
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 player
// who wins the game
void FindwinnerOfGame(string& S)
{
// Stores total count
// of 0s in the string
int cntZero = 0;
// Stores count of
// consecutive 1s
int cntConOne = 0;
// Stores Nim-Sum on count
// of consecutive 1s
int nimSum = 0;
// Stores length
// of the string
int N = S.length();
// Traverse the string
for (int i = 0; i < N; i++) {
// If the current
// character is 1
if (S[i] == '1') {
// Update cntConOne
cntConOne += 1;
}
else {
// Update nimSum
nimSum ^= cntConOne;
// Update cntConOne
cntConOne = 0;
// Update cntZero
cntZero++;
}
}
// Update nimSum
nimSum ^= cntConOne;
// If countZero is
// an even number
if (cntZero % 2 == 0) {
cout << "Tie";
}
// nimSum is not 0
else if (nimSum) {
cout << "player 1";
}
// If nimSum is zero
else {
cout << "player 2";
}
}
// Driver Code
int main()
{
string S = "0110011";
FindwinnerOfGame(S);
}
Java
// Java program to implement
// the above approach
// Function to find the player
// who wins the game
class GFG {
public static void FindwinnerOfGame(String S)
{
// Stores total count
// of 0s in the string
int cntZero = 0;
// Stores count of
// consecutive 1s
int cntConOne = 0;
// Stores Nim-Sum on count
// of consecutive 1s
int nimSum = 0;
// Stores length
// of the string
int N = S.length();
// Traverse the string
for (int i = 0; i < N; i++) {
// If the current
// character is 1
if (S.charAt(i) == '1') {
// Update cntConOne
cntConOne += 1;
}
else {
// Update nimSum
nimSum ^= cntConOne;
// Update cntConOne
cntConOne = 0;
// Update cntZero
cntZero++;
}
}
// Update nimSum
nimSum ^= cntConOne;
// If countZero is
// an even number
if (cntZero % 2 == 0) {
System.out.print("Tie");
}
// nimSum is not 0
else if (nimSum != 0) {
System.out.print("player 1");
}
// If nimSum is zero
else {
System.out.print("player 2");
}
}
// Driver Code
public static void main(String[] args)
{
String S = "0110011";
FindwinnerOfGame(S);
}
}
// This code is contributed by grand_master.
Python3
# Python 3 program to implement
# the above approach
# Function to find the player
# who wins the game
def FindwinnerOfGame(S):
# Stores total count
# of 0s in the string
cntZero = 0
# Stores count of
# consecutive 1s
cntConOne = 0
# Stores Nim-Sum on count
# of consecutive 1s
nimSum = 0
# Stores length
# of the string
N = len(S)
# Traverse the string
for i in range(N):
# If the current
# character is 1
if (S[i] == '1'):
# Update cntConOne
cntConOne += 1
else:
# Update nimSum
nimSum ^= cntConOne
# Update cntConOne
cntConOne = 0
# Update cntZero
cntZero += 1
# Update nimSum
nimSum ^= cntConOne
# If countZero is
# an even number
if (cntZero % 2 == 0):
print("Tie")
# nimSum is not 0
elif(nimSum):
print("player 1")
# If nimSum is zero
else:
print("player 2")
# Driver Code
if __name__ == '__main__':
S = "0110011"
FindwinnerOfGame(S)
# this code is contributed by SURENDRA_GANGWAR.
C#
// C# program to implement
// the above approach
using System;
// Function to find the player
// who wins the game
class GFG {
public static void FindwinnerOfGame(string S)
{
// Stores total count
// of 0s in the string
int cntZero = 0;
// Stores count of
// consecutive 1s
int cntConOne = 0;
// Stores Nim-Sum on count
// of consecutive 1s
int nimSum = 0;
// Stores length
// of the string
int N = S.Length;
// Traverse the string
for (int i = 0; i < N; i++) {
// If the current
// character is 1
if (S[i] == '1') {
// Update cntConOne
cntConOne += 1;
}
else {
// Update nimSum
nimSum ^= cntConOne;
// Update cntConOne
cntConOne = 0;
// Update cntZero
cntZero++;
}
}
// Update nimSum
nimSum ^= cntConOne;
// If countZero is
// an even number
if (cntZero % 2 == 0) {
Console.Write("Tie");
}
// nimSum is not 0
else if (nimSum != 0) {
Console.Write("player 1");
}
// If nimSum is zero
else {
Console.Write("player 2");
}
}
// Driver Code
public static void Main(string[] args)
{
string S = "0110011";
FindwinnerOfGame(S);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program of the above approach
// Function to find the player
// who wins the game
function FindwinnerOfGame(S)
{
// Stores total count
// of 0s in the string
let cntZero = 0;
// Stores count of
// consecutive 1s
let cntConOne = 0;
// Stores Nim-Sum on count
// of consecutive 1s
let nimSum = 0;
// Stores length
// of the string
let N = S.length;
// Traverse the string
for (let i = 0; i < N; i++) {
// If the current
// character is 1
if (S[i] == '1') {
// Update cntConOne
cntConOne += 1;
}
else {
// Update nimSum
nimSum ^= cntConOne;
// Update cntConOne
cntConOne = 0;
// Update cntZero
cntZero++;
}
}
// Update nimSum
nimSum ^= cntConOne;
// If countZero is
// an even number
if (cntZero % 2 == 0) {
document.write("Tie");
}
// nimSum is not 0
else if (nimSum != 0) {
document.write("player 1");
}
// If nimSum is zero
else {
document.write("player 2");
}
}
// Driver Code
let S = "0110011";
FindwinnerOfGame(S);
</script>
Producción:
player 2
Complejidad de tiempo: O(N), donde N es la longitud de la string
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA