Un juego de cuerdas binarias

Dada una string binaria S . La tarea es determinar el ganador del juego cuando dos jugadores juegan un juego de manera óptima con la cuerda según las condiciones dadas:

• El jugador 1 siempre comienza primero.
• Dos jugadores se turnan para elegir un bloque completo de caracteres iguales consecutivos y eliminarlos de una String S binaria determinada.
• El jugador 1 puede elegir solo un número impar de caracteres iguales consecutivos y el jugador 2 puede elegir solo un número par de caracteres iguales consecutivos. El jugador no puede elegir nada y contarlo como su turno solo si es imposible elegir nada.
• Después de eliminar todos los personajes, el jugador con puntajes máximos gana el juego y si los puntajes son iguales, imprime «-1»

Entrada: S = “1110011001010”
Salida: Jugador 1
Explicación: 
Los caracteres seleccionados estarán en negrita y la puntuación del Jugador 1 es Puntuación_1 y la puntuación del Jugador 2 es Puntuación_2:
Turno 1: (Jugador 1) “ 111 0011001010” → “0011001010” Puntuación_1 = 3
Turno 2: (Jugador 2) “00 11 001010” → “00001010” Puntuación_2 = 2
Turno 3: (Jugador 1) “0000 1 010”→ “0000010” Puntuación_1 = 4
Turno 4: (Jugador 2) “0000010” 
Él no puede hacer nada ya que solo está presente un ‘1’, que es un número impar. 
Además, no puede elegir los ‘0’ ya que son impares (5 y 1), por lo tanto, Puntuación_2 = 2
Turno 5: (Jugador 1) «00000 1 0″ → «000000» Puntuación_1 = 5
Turno 6: (Jugador 2) “ 000000 ” → “” Score_2 = 2 (Ningún ‘1’ fue eliminado en este turno)

Puntajes finales: Puntaje_1 = 5 y Puntaje_2 = 2
Por lo tanto, el jugador 1 gana.

Entrada: S=“11111101”
Salida: Jugador 2
Explicación: 
Turno 1: (Jugador 1) “1111110 1 ” → “1111110” Puntuación_1 = 3
Turno 2: (Jugador 2) “ 111111 0” → “0” Puntuación_2 = 6
Turno 3: (Jugador 1) “ 0 ” → “” Puntuación_1 = 3

Puntajes finales: Puntaje_1 = 3 y Puntaje_2 = 6
Por lo tanto, el jugador 2 gana.

Acercarse: 

1. Si observamos detenidamente este juego, entendemos que los únicos 1 consecutivos contribuyen a las puntuaciones de estos jugadores.
2. Cree una lista para almacenar las longitudes de los 1 consecutivos en la string.
3. Ordena la lista en orden descendente.
4. Ahora itere sobre la lista y si el elemento de la lista es impar, se agregará a la puntuación del jugador 1 y, si es par, se agregará a la puntuación del jugador 2 .
5. Ahora, si la puntuación del jugador 1 es mayor que la puntuación del jugador 2, imprima «Jugador 1» y si la puntuación del jugador 2 es mayor que la puntuación del jugador 1, imprima «Jugador 2» .
6. Escriba “-1” si hay un empate, es decir, las puntuaciones son las mismas.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the result of
// the game
string gameMax(string S)
{
     
    // length of the string
    int N = S.length();
  
    // List to maintain the lengths of
    // consecutive '1's in the string
    vector<int> list;
  
    // Variable that keeps a track of
    // the current length of the block
    // of consecutive '1's
    int one = 0;
  
    for(int i = 0; i < N; i++)
    {
        if (S[i] == '1')
        {
            one++;
        }
        else
        {
             
            // Adds non-zero lengths
            if (one != 0)
            {
                list.push_back(one);
            }
            one = 0;
        }
    }
  
    // This takes care of the case
    // when the last character is '1'
    if (one != 0)
    {
        list.push_back(one);
    }
  
    // Sorts the lengths in
    // descending order
    sort(list.begin(), list.end(),
         greater<int>());
  
    // Scores of the 2 players
    int score_1 = 0, score_2 = 0;
  
    for(int i = 0; i < list.size(); i++)
    {
         
        // For player 1
        if (list[i] % 2 == 1)
        {
            score_1 += list[i];
        }
  
        // For player 2
        else
        {
            score_2 += list[i];
        }
    }
  
    // In case of a tie
    if (score_1 == score_2)
        return "-1";
  
    // Print the result
    return (score_1 > score_2) ? "Player 1" :
                                 "Player 2";
}
 
// Driver Code
int main()
{
     
    // Given string S
    string S = "11111101";
  
    // Function call
    cout << gameMax(S);
}
 
// This code is contributed by rutvik_56

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to return the result of
    // the game
    public static String gameMax(String S)
    {
        // length of the string
        int N = S.length();
 
        // List to maintain the lengths of
        // consecutive '1's in the string
        List<Integer> list = new ArrayList<>();
 
        // Variable that keeps a track of
        // the current length of the block
        // of consecutive '1's
        int one = 0;
 
        for (int i = 0; i < N; i++) {
 
            if (S.charAt(i) == '1') {
                one++;
            }
            else {
 
                // Adds non-zero lengths
                if (one != 0) {
                    list.add(one);
                }
                one = 0;
            }
        }
 
        // This takes care of the case
        // when the last character is '1'
        if (one != 0) {
            list.add(one);
        }
 
        // Sorts the lengths in
        // descending order
        Collections.sort(list,
                         Collections.reverseOrder());
 
        // Scores of the 2 players
        int score_1 = 0, score_2 = 0;
 
        for (int i = 0; i < list.size(); i++) {
 
            // For player 1
            if (list.get(i) % 2 == 1) {
                score_1 += list.get(i);
            }
 
            // For player 2
            else {
                score_2 += list.get(i);
            }
        }
 
        // In case of a tie
        if (score_1 == score_2)
            return "-1";
 
        // Print the result
        return (score_1 > score_2) ? "Player 1"
                                   : "Player 2";
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given string S
        String S = "11111101";
 
        // Function Call
        System.out.println(gameMax(S));
    }
}

# Python3 program for
# the above approach
 
# Function to return the
# result of the game
def gameMax(S):
 
    # Length of the string
    N = len(S)
 
    # List to maintain the lengths of
    # consecutive '1's in the string
    list = []
 
    # Variable that keeps a track of
    # the current length of the block
    # of consecutive '1's
    one = 0
     
    for i in range(N):
        if(S[i] == '1'):
            one += 1
        else:
 
            # Adds non-zero lengths
            if(one != 0):
                list.append(one)
            one = 0
 
    # This takes care of the case
    # when the last character is '1'
    if(one != 0):
        list.append(one)
 
    # Sorts the lengths in
    # descending order
    list.sort(reverse = True)
 
    # Scores of the 2 players
    score_1 = 0
    score_2 = 0
 
    for i in range(len(list)):
 
        # For player 1
        if(list[i] % 2 == 1):
            score_1 += list[i]
 
        # For player 2
        else:
            score_2 += list[i]
 
    # In case of a tie
    if(score_1 == score_2):
        return '-1'
 
    # Print the result
    if(score_1 > score_2):
        return "Player 1"
    else:
        return "Player 2"
 
# Driver Code
 
# Given string S
S = "11111101"
 
# Function call
print(gameMax(S))
 
# This code is contributed by avanitrachhadiya2155

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the result of
// the game
public static String gameMax(String S)
{
     
    // length of the string
    int N = S.Length;
 
    // List to maintain the lengths of
    // consecutive '1's in the string
    List<int> list = new List<int>();
 
    // Variable that keeps a track of
    // the current length of the block
    // of consecutive '1's
    int one = 0;
 
    for(int i = 0; i < N; i++)
    {
        if (S[i] == '1')
        {
            one++;
        }
        else
        {
 
            // Adds non-zero lengths
            if (one != 0)
            {
                list.Add(one);
            }
            one = 0;
        }
    }
 
    // This takes care of the case
    // when the last character is '1'
    if (one != 0)
    {
        list.Add(one);
    }
 
    // Sorts the lengths in
    // descending order
    list.Sort();
    list.Reverse();
     
    // Scores of the 2 players
    int score_1 = 0, score_2 = 0;
 
    for(int i = 0; i < list.Count; i++)
    {
         
        // For player 1
        if (list[i] % 2 == 1)
        {
            score_1 += list[i];
        }
 
        // For player 2
        else
        {
            score_2 += list[i];
        }
    }
 
    // In case of a tie
    if (score_1 == score_2)
        return "-1";
 
    // Print the result
    return (score_1 > score_2) ?
         "Player 1" : "Player 2";
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given string S
    String S = "11111101";
 
    // Function Call
    Console.WriteLine(gameMax(S));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// javascript program for the
// above approach
 
// Function to return the result of
// the game
function gameMax(S)
{
      
    // length of the string
    let N = S.length;
  
    // List to maintain the lengths of
    // consecutive '1's in the string
    let list = [];
  
    // Variable that keeps a track of
    // the current length of the block
    // of consecutive '1's
    let one = 0;
  
    for(let i = 0; i < N; i++)
    {
        if (S[i] == '1')
        {
            one++;
        }
        else
        {
  
            // Adds non-zero lengths
            if (one != 0)
            {
                list.push(one);
            }
            one = 0;
        }
    }
  
    // This takes care of the case
    // when the last character is '1'
    if (one != 0)
    {
        list.push(one);
    }
  
    // Sorts the lengths in
    // descending order
    list.sort();
    list.reverse();
      
    // Scores of the 2 players
    let score_1 = 0, score_2 = 0;
  
    for(let i = 0; i < list.length; i++)
    {
          
        // For player 1
        if (list[i] % 2 == 1)
        {
            score_1 += list[i];
        }
  
        // For player 2
        else
        {
            score_2 += list[i];
        }
    }
  
    // In case of a tie
    if (score_1 == score_2)
        return "-1";
  
    // Print the result
    return (score_1 > score_2) ?
         "Player 1" : "Player 2";
}
  
// Driver Code
 
    // Given string S
    let S = "11111101";
  
    // Function Call
    document.write(gameMax(S));
    
   // This code is contributed by target_2.
</script>

Producción: 

Player 2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)