Dada una string binaria str que consta solo de 0 y 1 , donde 0 representa una posición desocupada y 1 representa una posición ocupada. Dos jugadores A y B tienen que ocupar una posición desocupada (convertir 0 a 1) turno por turno siguiendo las reglas dadas:
- El jugador solo puede ocupar la posición desocupada
- El jugador solo puede moverse a su posición adyacente en cada turno.
Si un jugador no puede hacer un movimiento en el turno, pierde. Prediga el ganador del juego si ambos juegan de manera óptima dado que A hace el primer movimiento.
Ejemplo:
Entrada: str=”1000″
Salida: A
Explicación: A hace el primer movimiento y ocupa la posición en el segundo índice de la string (índice basado en 0), luego, independientemente de la posición que elija B, solo quedará una posición desocupada que estará ocupada por A en el próximo turno y B no puede hacer más movimientos, por lo que A gana.Entrada: str=”1001″
Salida: B
Acercarse:
- Encuentre la longitud de las dos substrings más largas de posiciones iniciales desocupadas (es decir, substring de 0s ).
- Si la longitud de la substring más grande es par , entonces B será el ganador independientemente de la longitud de la segunda substring más grande. Esto se debe a que A siempre ocupará la ranura central de la substring más grande, por lo que en este caso tendrá el mismo número de ranuras para el movimiento que le quedan a B en la substring dada. A necesita más espacios que B para ganar el juego, mientras que en este caso, ambos tienen el mismo número de espacios, por lo que A perderá.
- Si la longitud de la substring más grande es impar , puede haber dos casos:
- Si la longitud de la segunda substring más grande es menor que el número de ranuras de A en la substring más grande (es decir , (n/2) + 1 donde n es el tamaño de la substring), entonces A será el ganador ya que B siempre tener un número menor de ranuras que A , independientemente de su decisión inicial (elegir entre la substring más grande o la segunda más grande).
- De lo contrario, B será el ganador, ya que B puede elegir la segunda substring más grande para realizar el movimiento inicial y tendrá más espacios disponibles para movimientos posteriores que A.
- Escriba la respuesta de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <math.h>
using namespace std;
// Function to predict the winner
string predictWinner(string s)
{
int n = s.length();
int max1 = 0, max2 = 0;
int curr = 0;
// Loop through the string to find out
// lengths of longest two substrings of 0s
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
curr++;
}
else {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1)
&& (curr > max2)) {
max2 = curr;
}
curr = 0;
}
}
if (curr > 0) {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1)
&& (curr > max2)) {
max2 = curr;
}
}
// If longest substring
// of 0s is of even length
// then B will always be the winner
if (max1 % 2 == 0) {
return "B";
}
// Slot for A's moves
// will be half the total
// number of slots plus
// one in longest substring
int left = ceil((float)max1 / 2);
// If slots for A's moves
// are more than slots in
// second largest substring
// then A will be the
// winner else B will be winner
if (left > max2) {
return "A";
}
return "B";
}
// Driver Code
int main()
{
string s = "1000";
string ans = predictWinner(s);
cout << ans;
return 0;
}
C
// C program for the above approach
#include <math.h>
#include <stdio.h>
// Function to predict the winner
char predictWinner(char s[], int n)
{
int max1 = 0, max2 = 0;
int curr = 0;
// Loop through the string to find out
// lengths of longest two substrings of 0s
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
curr++;
}
else {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
curr = 0;
}
}
if (curr > 0) {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
}
// If longest substring
// of 0s is of even length
// then B will always be the winner
if (max1 % 2 == 0) {
return 'B';
}
// Slot for A's moves
// will be half the total
// number of slots plus
// one in longest substring
int left = ceil((float)max1 / 2);
// If slots for A's moves
// are more than slots in
// second largest substring
// then A will be the
// winner else B will be winner
if (left > max2) {
return 'A';
}
return 'B';
}
// Driver Code
int main()
{
char s[] = "1000";
int n = 4;
char ans = predictWinner(s, n);
printf("%c", ans);
return 0;
}
// This code is contributed by saxenaanjali239.
Java
// Java program for the above approach
import java.lang.Math;
import java.util.*;
public class GeeksForGeeks
{
// Function to predict the winner
public static String predictWinner(String s)
{
int n = s.length();
int max1 = 0, max2 = 0;
int curr = 0;
// Loop through the string to find out
// lengths of longest two substrings of 0s
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
curr++;
}
else {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
curr = 0;
}
}
if (curr > 0) {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
}
// If longest substring
// of 0s is of even length
// then B will always be the winner
if (max1 % 2 == 0) {
return "B";
}
// Slot for A's moves
// will be half the total
// number of slots plus
// one in longest substring
int left = (int)Math.ceil((float)max1 / 2);
// If slots for A's moves
// are more than slots in
// second largest substring
// then A will be the
// winner else B will be winner
if (left > max2) {
return "A";
}
return "B";
}
// Driver Code
public static void main(String args[])
{
String s = "1000";
String ans = predictWinner(s);
System.out.println(ans);
}
}
// This code is contributed by saxenaanjali239.
Python
# Python program for the above approach import math def predictWinner(s, n): max1 = 0 max2 = 0 curr = 0 i = 0 # Loop through the string to find out # lengths of longest two substrings of 0s for i in range(n): if s[i] == '0': curr += 1 else: if max1 <= curr: max2 = max1 max1 = curr elif (curr < max1) and (curr > max2): max2 = curr curr = 0 if curr > 0: if max1 <= curr: max2 = max1 max1 = curr elif (curr < max1) and (curr > max2): max2 = curr # If longest substring # of 0s is of even length # then B will always be the winner if max1 % 2 == 0: return "B" # Slot for A's moves # will be half the total # number of slots plus # one in longest substring left = math.ceil(max1 / 2) # If slots for A's moves # are more than slots in # second largest substring # then A will be the # winner else B will be winner if left > max2: return "A" return "B" # Driver program to test the above function s = "1000" n = len(s) ans = predictWinner(s, n) print(ans) # This code is contributed by saxenaanjali239.
C#
// C# program for the above approach
using System;
class GeeksForGeeks
{
// Function to predict the winner
static string predictWinner(string s)
{
int n = s.Length;
int max1 = 0, max2 = 0;
int curr = 0;
// Loop through the string to find out
// lengths of longest two substrings of 0s
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
curr++;
}
else {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
curr = 0;
}
}
if (curr > 0) {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
}
// If longest substring
// of 0s is of even length
// then B will always be the winner
if (max1 % 2 == 0) {
return "B";
}
// Slot for A's moves
// will be half the total
// number of slots plus
// one in longest substring
int left = (int)Math.Ceiling((float)max1 / 2);
// If slots for A's moves
// are more than slots in
// second largest substring
// then A will be the
// winner else B will be winner
if (left > max2) {
return "A";
}
return "B";
}
// Driver Code
public static void Main()
{
string s = "1000";
string ans = predictWinner(s);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to predict the winner
function predictWinner(s)
{
let n = s.length;
let max1 = 0, max2 = 0;
let curr = 0;
// Loop through the string to find out
// lengths of longest two substrings of 0s
for (let i = 0; i < n; i++) {
if (s[i] == '0') {
curr++;
}
else {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
curr = 0;
}
}
if (curr > 0) {
if (max1 <= curr) {
max2 = max1;
max1 = curr;
}
else if ((curr < max1) && (curr > max2)) {
max2 = curr;
}
}
// If longest substring
// of 0s is of even length
// then B will always be the winner
if (max1 % 2 == 0) {
return "B";
}
// Slot for A's moves
// will be half the total
// number of slots plus
// one in longest substring
let left = Math.ceil(max1 / 2);
// If slots for A's moves
// are more than slots in
// second largest substring
// then A will be the
// winner else B will be winner
if (left > max2) {
return "A";
}
return "B";
}
// Driver Code
let s = "1000";
let ans = predictWinner(s);
document.write(ans);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
A
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saxenaanjali239 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA