Dada una string S de longitud N que contiene letras en minúsculas. Dos jugadores A y B juegan un juego de manera óptima por turnos, comenzando con el jugador A. En cada movimiento, se puede realizar cualquiera de las siguientes operaciones:
- Elimina una consonante de la string.
- Si algún carácter es una vocal , entonces conviértalo en cualquier otro alfabeto.
Un jugador pierde el juego si hay un número par de consonantes y no quedan vocales en la string. La tarea es determinar el ganador del juego. En caso de empate, imprima D .
Ejemplos:
Input: S = "abcd" Output: Player A Explanation: Player A can win by performing the following moves: Move 1: A changes a to f. Therefore, S = "fbcd" Move 2: B removes f. Therefore, S = "bcd". Move 3: A removes b. Therefore, S = "cd". Move 4: B removes c. Therefore, S = "d". Move 5: A removes d. Therefore, S = "". Now in B's turn, S have no vowels and an even number of consonants i.e., 0.
Input: S = "abcde" Output: D
Planteamiento: Para resolver el problema, observe los siguientes casos:
- Si no hay vocales y hay un número par de consonantes en la string, el jugador que comienza el juego pierde el juego , es decir, el jugador B gana.
- Si no hay vocales y hay un número impar de consonantes en la string, entonces el jugador que comienza el juego gana el juego , es decir, el jugador A gana.
- Si una sola vocal y un número impar de consonantes están presentes en la cuerda dada, el jugador A puede ganar.
- Si hay más de una vocal presente en la string, es un empate.
Siga los pasos a continuación para resolver el problema:
- Cuente el número de consonantes en la string S dada y guárdelo en una variable, digamos X .
- Por lo tanto, el número de vocales en la string dada S es igual a N – X.
- Imprima D si N – X es mayor que 1 .
- Imprima el jugador B si N – X es 0 y X es par.
- De lo contrario, imprima el jugador A .
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 a winner of the game
// if both the player plays optimally
void findWinner(string s)
{
// Stores the count of vowels
// and consonants
int vowels_count = 0,
consonants_count = 0;
// Traverse the string
for (int i = 0; i < s.size(); i++) {
// Check if character is vowel
if (s[i] == 'a'
|| s[i] == 'e'
|| s[i] == 'i'
|| s[i] == 'o'
|| s[i] == 'u') {
// Increment vowels count
vowels_count++;
}
// Otherwise increment the
// consonants count
else {
consonants_count++;
}
}
if (vowels_count == 0) {
// Check if Player B wins
if (consonants_count % 2 == 0) {
cout << "Player B";
}
// Check if Player A wins
else {
cout << "Player A";
}
}
// Check if Player A wins
else if (vowels_count == 1
&& consonants_count % 2 != 0) {
cout << "Player A";
}
// If game ends in a Draw
else {
cout << "D";
}
}
// Driver Code
int main()
{
// Given string s
string s = "abcd";
// Function Call
findWinner(s);
return 0;
}
Java
// Java program for the
// above approach
class GFG{
// Function to find a winner
// of the game if both the
// player plays optimally
static void findWinner(char[] s)
{
// Stores the count of vowels
// and consonants
int vowels_count = 0,
consonants_count = 0;
// Traverse the String
for (int i = 0; i < s.length; i++)
{
// Check if character is vowel
if (s[i] == 'a' ||
s[i] == 'e' ||
s[i] == 'i' ||
s[i] == 'o' ||
s[i] == 'u')
{
// Increment vowels count
vowels_count++;
}
// Otherwise increment the
// consonants count
else
{
consonants_count++;
}
}
if (vowels_count == 0)
{
// Check if Player B wins
if (consonants_count % 2 == 0)
{
System.out.print("Player B");
}
// Check if Player A wins
else
{
System.out.print("Player A");
}
}
// Check if Player A wins
else if (vowels_count == 1 &&
consonants_count % 2 != 0)
{
System.out.print("Player A");
}
// If game ends in a Draw
else
{
System.out.print("D");
}
}
// Driver Code
public static void main(String[] args)
{
// Given String s
String s = "abcd";
// Function Call
findWinner(s.toCharArray());
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find a winner of the game
# if both the player plays optimally
def findWinner(s):
# Stores the count of
# vowels and consonants
vowels_count = 0
consonants_count = 0
# Traverse the string
p = len(s)
for i in range(0, p):
# Check if character is vowel
if (s[i] == 'a' or s[i] == 'e' or
s[i] == 'i' or s[i] == 'o' or
s[i] == 'u'):
# Increment vowels count
vowels_count = vowels_count + 1
# Otherwise increment the
# consonants count
else:
consonants_count = consonants_count + 1
if (vowels_count == 0):
# Check if Player B wins
if (consonants_count % 2 == 0):
print("Player B")
# Check if Player A wins
else:
print("Player A")
# Check if Player A wins
elif (vowels_count == 1 and
consonants_count % 2 != 0):
print("Player A")
# If game ends in a Draw
else:
print("D")
# Driver Code
s = "abcd"
findWinner(s)
# This code is contributed by sallagondaavinashreddy7
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find a winner
// of the game if both the
// player plays optimally
static void findWinner(char[] s)
{
// Stores the count of vowels
// and consonants
int vowels_count = 0,
consonants_count = 0;
// Traverse the String
for (int i = 0; i < s.Length; i++)
{
// Check if character is vowel
if (s[i] == 'a' ||
s[i] == 'e' ||
s[i] == 'i' ||
s[i] == 'o' ||
s[i] == 'u')
{
// Increment vowels count
vowels_count++;
}
// Otherwise increment the
// consonants count
else
{
consonants_count++;
}
}
if (vowels_count == 0)
{
// Check if Player B wins
if (consonants_count % 2 == 0)
{
Console.Write("Player B");
}
// Check if Player A wins
else
{
Console.Write("Player A");
}
}
// Check if Player A wins
else if (vowels_count == 1 &&
consonants_count % 2 != 0)
{
Console.Write("Player A");
}
// If game ends in a Draw
else
{
Console.Write("D");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given String s
String s = "abcd";
// Function Call
findWinner(s.ToCharArray());
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Function to find a winner of the game
// if both the player plays optimally
function findWinner(s)
{
// Stores the count of vowels
// and consonants
var vowels_count = 0,
consonants_count = 0;
// Traverse the string
for (var i = 0; i < s.length; i++)
{
// Check if character is vowel
if (
s[i] === "a" ||
s[i] === "e" ||
s[i] === "i" ||
s[i] === "o" ||
s[i] === "u"
)
{
// Increment vowels count
vowels_count++;
}
// Otherwise increment the
// consonants count
else
{
consonants_count++;
}
}
if (vowels_count === 0)
{
// Check if Player B wins
if (consonants_count % 2 === 0)
{
document.write("Player B");
}
// Check if Player A wins
else
{
document.write("Player A");
}
}
// Check if Player A wins
else if (vowels_count === 1 && consonants_count % 2 !== 0) {
document.write("Player A");
}
// If game ends in a Draw
else {
document.write("D");
}
}
// Driver Code
// Given string s
var s = "abcd";
// Function Call
findWinner(s);
// This codeis contributed by rdtank.
</script>
Producción
Player A
Complejidad de tiempo: O(N) //solo se requiere un recorrido de la string.
Espacio auxiliar: O (1) // no se usa una array adicional, por lo que el espacio es constante.
Publicación traducida automáticamente
Artículo escrito por bolliranadheer y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA