Hay dos jugadores A y B y una pila de N cartas apiladas una sobre otra. La tarea es encontrar al ganador del juego, suponiendo que ambos jugadores jueguen de manera óptima según las siguientes pautas:
- El jugador A siempre comienza el juego y los jugadores toman turnos alternos posteriormente.
- En cada turno, un jugador puede retirar K ( 1 ≤ K ≤ N) cartas si K & n = 0, donde n es el tamaño de la pila actual.
- Si un jugador no puede hacer un movimiento en ningún momento del juego, ese jugador pierde y el juego termina.
Ejemplos:
Entrada: N = 1
Salida: B
Explicación:
A solo puede quitar 1 carta, pero 1 y 1 = 1, por lo que A no puede hacer un movimiento.
Por lo tanto, B gana el juego.Entrada: N = 4
Salida: A
Explicación:
A quitará 3 cartas como 3 y 4 = 0, ahora solo queda 1 carta y B no puede hacer un movimiento.
Por lo tanto, A gana el juego.
Enfoque: La idea se basa en la observación de que si la cuenta de 1 en la representación binaria de N , antes de encontrar un 0 , es impar, entonces A gana el juego. Si no existe tal combinación de 1 y 0 en toda la string binaria, entonces B gana. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable countOne para almacenar el recuento de 1 .
- Convierta N en su representación binaria y guárdelo en una string, binString .
- Atraviese la string binString y haga lo siguiente:
- Si se encuentra ‘ 1 ‘, incremente countOne .
- Si se encuentra ‘ 0 ‘, verifique si CountOne es par o impar, si CountOne es impar A gana y salga del bucle ; de lo contrario, restablezca CountOne a 0 y continúe atravesando.
- Si toda la cuerda se atraviesa sin romperse, entonces B gana.
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 winner of the
// game if both player plays optimally
void findWinner(int N)
{
// Stores the count of 1s
int onesBeforeZero = 0;
int flag = 1;
// Convert N to binary representation
int binString[32];
int i = 0;
while (N > 0)
{
// Storing remainder in binary array
binString[i] = N % 2;
N = N / 2;
i++;
}
int l = sizeof(binString) /
sizeof(binString[0]);
// Traverse the binary string
for(int j = 0; j < l; j++)
{
// If 1 is encountered,
// increment count of 1s
if (binString[j] == 1)
{
onesBeforeZero += 1;
}
// If 0 is encountered, check
// if count of 1s is odd
else
{
// If count of 1s is odd,
// then winner is A
if (onesBeforeZero & 1)
{
cout << "A";
flag = 0;
break;
}
// If count of 1s is even,
// reset it to 0
else
onesBeforeZero = 0;
}
}
// If entire loop is traversed
// without breaking, then
// B is the winner
if (flag == 1)
cout << "B";
}
// Driver Code
int main()
{
int N = 4;
// Function Call
findWinner(N);
return 0;
}
// This code is contributed by jana_sayantan
C
// C program for the above approach
#include <stdio.h>
// Function to find the winner of the
// game if both player plays optimally
void findWinner(unsigned long long N)
{
// Stores the count of 1s
int onesBeforeZero = 0;
int flag = 1, j = 0;
char binString[32];
// Converting N into a binary string
for(int i = 31; i >= 0; i--)
{
unsigned long long temp = N >> i;
if (temp & 1)
binString[j] = '1';
else
binString[j] = '0';
j += 1;
}
// Traverse the binary string
for(int i = 0; i < 32; i++)
{
if (binString[i] == '1')
// If 1 is encountered
// increment ones count
onesBeforeZero += 1;
else
{
// If 0 is encountered check
// if ones count is odd
if (onesBeforeZero & 1)
{
// If ones count is odd
// winner is A break
printf("A");
flag = 0;
break;
}
else
// If ones count is even
// reset it to 0 and continue
onesBeforeZero = 0;
}
}
// If entire loop is traversed
// without breaking, then
// B is the winner
if (flag == 1)
printf("B");
}
// Driver code
int main()
{
unsigned long long N = 4;
// Function Call
findWinner(N);
return 0;
}
// This code is contributed by Praneeth Kapila
Java
// Java program for the above approach
class GFG{
// Function to find the winner
static void findWinner(long N)
{
// Stores the count of 1s
int onesBeforeZero = 0, flag = 1, j = 0;
String[] binString = new String[32];
// Converting N into a binary string
for(int i = 31; i >= 0; i--)
{
long temp = N >> i;
if ((temp & 1) == 1)
binString[j] = "1";
else
binString[j] = "0";
j += 1;
}
for(int i = 0; i < 32; i++)
{
if (binString[i] == "1")
// If 1 is encountered
// increment ones count
onesBeforeZero += 1;
else
{
// If 0 is encountered check
//if ones count is odd
if ((onesBeforeZero & 1) == 1)
{
// If ones count is odd winner
// is A break
System.out.println("A");
flag = 0;
break;
}
else
// If ones count is even
// reset it to 0 and continue
onesBeforeZero = 0;
}
}
// If entire loop is traversed
// without breaking, then
// B is the winner
if (flag == 1)
System.out.println("B");
}
// Driver code
public static void main(String[] args)
{
long N = 4;
// Function Call
findWinner(N);
}
}
// This code is contributed by Praneeth Kapila
Python3
# Python3 program for the above approach
# Function to find the winner of the
# game if both player plays optimally
def findWinner(N):
# Stores the count of 1s
onesBeforeZero = 0
flag = 1
# Convert N to binary representation
binString = bin(N).replace("0b", "")
l = len(binString)
# Traverse the binary string
for j in range(l):
# If 1 is encountered,
# increment count of 1s
if binString[j] == '1':
onesBeforeZero += 1
# If 0 is encountered, check
# if count of 1s is odd
else:
# If count of 1s is odd,
# then winner is A
if onesBeforeZero & 1:
print("A")
flag = 0
break
# If count of 1s is even,
# reset it to 0
else:
onesBeforeZero = 0
# If entire loop is traversed
# without breaking, then
# B is the winner
if flag == 1:
print("B")
# Driver Code
N = 4
# Function Call
findWinner(N)
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the winner
static void findWinner(long N)
{
// Stores the count of 1s
int onesBeforeZero = 0, flag = 1, j = 0;
String[] binString = new String[32];
// Converting N into a binary string
for(int i = 31; i >= 0; i--)
{
long temp = N >> i;
if ((temp & 1) == 1)
binString[j] = "1";
else
binString[j] = "0";
j += 1;
}
for(int i = 0; i < 32; i++)
{
if (binString[i] == "1")
// If 1 is encountered
// increment ones count
onesBeforeZero += 1;
else
{
// If 0 is encountered check
//if ones count is odd
if ((onesBeforeZero & 1) == 1)
{
// If ones count is odd winner
// is A break
Console.WriteLine("A");
flag = 0;
break;
}
else
// If ones count is even
// reset it to 0 and continue
onesBeforeZero = 0;
}
}
// If entire loop is traversed
// without breaking, then
// B is the winner
if (flag == 1)
Console.WriteLine("B");
}
// Driver code
public static void Main(String[] args)
{
long N = 4;
// Function Call
findWinner(N);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above approach
// Function to find the winner
function findWinner(N)
{
// Stores the count of 1s
let onesBeforeZero = 0, flag = 1, j = 0;
let binString = [];
// Converting N into a binary string
for(let i = 31; i >= 0; i--)
{
let temp = N >> i;
if ((temp & 1) == 1)
binString[j] = "1";
else
binString[j] = "0";
j += 1;
}
for(let i = 0; i < 32; i++)
{
if (binString[i] == "1")
// If 1 is encountered
// increment ones count
onesBeforeZero += 1;
else
{
// If 0 is encountered check
//if ones count is odd
if ((onesBeforeZero & 1) == 1)
{
// If ones count is odd winner
// is A break
document.write("A");
flag = 0;
break;
}
else
// If ones count is even
// reset it to 0 and continue
onesBeforeZero = 0;
}
}
// If entire loop is traversed
// without breaking, then
// B is the winner
if (flag == 1)
document.write("B");
}
// Driver code
let N = 4;
// Function Call
findWinner(N);
// This code is contributed by code_hunt
</script>
Producción:
A
Complejidad temporal: O(log N)
Espacio auxiliar: O(log N)
Publicación traducida automáticamente
Artículo escrito por praneethkapila y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA