estrategia óptima para un juego | Moneda de oro especial

Dada una fila de monedas de plata entre las que se encuentra presente una moneda especial de oro. Dos jugadores juegan el juego, y con cada movimiento, un jugador tiene que quitar una moneda del extremo izquierdo o derecho de la fila y el jugador que quita la moneda especial gana el juego. La tarea es encontrar al ganador del juego.

Ejemplos: 

Entrada: str = “GSSS” 
Salida: Primero 
El primer jugador retira directamente la moneda de oro especial.

Entrada: str = “SGS” 
Salida: Segundo 
Independientemente de la moneda que retire el primer jugador, la 
moneda de oro especial queda expuesta y el segundo jugador la retira. 
 

Enfoque: Se puede observar tomando algunos ejemplos que si el conteo de las monedas de plata es impar, entonces el primer jugador gana el juego; de lo contrario, el segundo jugador gana el juego. En un caso especial cuando la moneda de oro está en la esquina, el primer jugador será el ganador independientemente del número de monedas de plata.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// winner of the game
string getWinner(string str, int len)
{
     
    // To store the count of silver coins
    int total = 0;
     
    if(str[0]=='G' ||str[len-1]=='G')
        return "First";
    else{
        for (int i = 0; i < len; i++) {
 
            // Update the position of
           // the gold coin
            if (str[i] == 'S') {
                total++;
            }
        }
 
        // First player will win the game
        if ((total % 2) == 1)
            return "First";
        return "Second";
    }
}
 
// Driver code
int main()
{
    string str = "GSSS";
    int len = str.length();
 
    cout << getWinner(str, len);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the
// winner of the game
static String getWinner(String str, int len)
{
 
    // To store the count of silver coins
    int total = 0;
    for (int i = 0; i < len; i++)
    {
 
        // Update the position of
        // the gold coin
        if (str.charAt(i) == 'S')
        {
            total++;
        }
    }
 
    // First player will win the game
    if ((total % 2) == 1)
        return "First";
    return "Second";
}
 
// Driver code
public static void main(String []args)
{
    String str = "GSSS";
    int len = str.length();
 
    System.out.println(getWinner(str, len));
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 implementation of the approach
 
# Function to return the
# winner of the game
def getWinner(string, length) :
 
    # To store the count of silver coins
    total = 0;
    for i in range(length) :
 
        # Update the position of
        # the gold coin
        if (string[i] == 'S') :
            total += 1;
 
    # First player will win the game
    if ((total % 2) == 1) :
        return "First";
    return "Second";
 
# Driver code
if __name__ == "__main__" :
 
    string = "GSSS";
    length = len(string);
 
    print(getWinner(string, length));
     
# This code is contributed by kanugargng

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the
// winner of the game
static String getWinner(String str, int len)
{
 
    // To store the count of silver coins
    int total = 0;
    for (int i = 0; i < len; i++)
    {
 
        // Update the position of
        // the gold coin
        if (str[i] == 'S')
        {
            total++;
        }
    }
 
    // First player will win the game
    if ((total % 2) == 1)
        return "First";
    return "Second";
}
 
// Driver code
public static void Main(string []args)
{
    string str = "GSSS";
    int len = str.Length;
 
    Console.WriteLine(getWinner(str, len));
}
}
 
// This code is contributed by rrrtnx.

<script>
 
// Javascript implementation of the approach
 
// Function to return the
// winner of the game
function getWinner(str, len)
{
     
    // To store the count of silver coins
    var total = 0;
     
    if (str[0] == 'G' || str[len - 1] == 'G')
        return "First";
    else
    {
        for(var i = 0; i < len; i++)
        {
            // Update the position of
            // the gold coin
            if (str[i] == 'S')
            {
                total++;
            }
        }
 
        // First player will win the game
        if ((total % 2) == 1)
            return "First";
             
        return "Second";
    }
}
 
// Driver code
var str = "GSSS";
var len = str.length;
 
document.write(getWinner(str, len));
 
// This code is contributed by importantly
 
</script>

First