Dos jugadores están jugando una serie de juegos de piedra, papel o tijera . Hay un total de K juegos jugados. El jugador 1 tiene una secuencia de movimientos indicada por la string A y, de manera similar , el jugador 2 tiene la string B. Si algún jugador llega al final de su string, regresa al comienzo de la string. La tarea es contar el número de juegos ganados por cada uno de los jugadores cuando se juegan exactamente K juegos.
Ejemplos:
Entrada: k = 4, a = “SR”, b = “R”
Salida: 0 2
Juego 1: Jugador1 = S, Jugador2 = R, Ganador = Jugador2
Juego 2: Jugador1 = R, Jugador2 = R, Ganador = Empate
Juego 3: Jugador1 = S, Jugador2 = R, Ganador = Jugador2
Juego 4: Jugador1 = R, Jugador2 = R, Ganador = EmpateEntrada: k = 3, a = “S”, b = “SSS”
Salida: 0 0
Todos los juegos son sorteos.
Método: Sea n la longitud de la cuerda a y m la longitud de la cuerda b . La observación aquí es que los juegos se repetirían después de n * m movimientos. Entonces, podemos simular el proceso para n * m juegos y luego contar la cantidad de veces que se repite. Para los juegos restantes, podemos volver a simular el proceso, ya que ahora sería más pequeño que n * m . Por ejemplo, en el primer ejemplo anterior, n = 2 y m = 1 . Entonces, los juegos se repetirán después de cada n * m = 2 * 1 = 2 movimientos, es decir , (Jugador2, Empate) , (Jugador2, Empate) , …..,(Jugador2, Empate) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns 1 if first player wins,
// 0 in case of a draw and -1 if second player wins
int compare(char first, char second)
{
// If both players have the same move
// then it's a draw
if (first == second)
return 0;
if (first == 'R') {
if (second == 'S')
return 1;
else
return -1;
}
if (first == 'P') {
if (second == 'R')
return 1;
else
return -1;
}
if (first == 'S') {
if (second == 'P')
return 1;
else
return -1;
}
}
// Function that returns the count of games
// won by both the players
pair<int, int> countWins(int k, string a, string b)
{
int n = a.length();
int m = b.length();
int i = 0, j = 0;
// Total distinct games that can be played
int moves = n * m;
pair<int, int> wins = { 0, 0 };
while (moves--) {
int res = compare(a[i], b[j]);
// Player 1 wins the current game
if (res == 1)
wins.first++;
// Player 2 wins the current game
if (res == -1)
wins.second++;
i = (i + 1) % n;
j = (j + 1) % m;
}
// Number of times the above n * m games repeat
int repeat = k / (n * m);
// Update the games won
wins.first *= repeat;
wins.second *= repeat;
// Remaining number of games after
// removing repeated games
int rem = k % (n * m);
while (rem--) {
int res = compare(a[i], b[j]);
// Player 1 wins the current game
if (res == 1)
wins.first++;
// Player 2 wins the current game
if (res == -1)
wins.second++;
i = (i + 1) % n;
j = (j + 1) % m;
}
return wins;
}
// Driver code
int main()
{
int k = 4;
string a = "SR", b = "R";
auto wins = countWins(k, a, b);
cout << wins.first << " " << wins.second;
}
Java
// Java implementation of the above approach
import java.util.*;
import java.awt.Point;
class GFG{
// Function that returns 1 if first player wins,
// 0 in case of a draw and -1 if second player wins
public static int compare(char first, char second)
{
// If both players have the same move
// then it's a draw
if (first == second)
return 0;
if (first == 'R')
{
if (second == 'S')
return 1;
else
return -1;
}
if (first == 'P')
{
if (second == 'R')
return 1;
else
return -1;
}
if (first == 'S')
{
if (second == 'P')
return 1;
else
return -1;
}
return 0;
}
// Function that returns the count of games
// won by both the players
public static Point countWins(int k, String a,
String b)
{
int n = a.length();
int m = b.length();
int i = 0, j = 0;
// Total distinct games that
// can be played
int moves = n * m;
Point wins = new Point (0, 0);
while (moves-- > 0)
{
int res = compare(a.charAt(i),
b.charAt(j));
// Player 1 wins the current game
if (res == 1)
wins = new Point(wins.x + 1,
wins.y);
// Player 2 wins the current game
if (res == -1)
wins = new Point(wins.x,
wins.y + 1);
i = (i + 1) % n;
j = (j + 1) % m;
}
// Number of times the above
// n * m games repeat
int repeat = k / (n * m);
// Update the games won
wins = new Point(wins.x * repeat,
wins.y * repeat);
// Remaining number of games after
// removing repeated games
int rem = k % (n * m);
while (rem-- > 0)
{
int res = compare(a.charAt(i),
b.charAt(j));
// Player 1 wins the current game
if (res == 1)
wins = new Point(wins.x + 1,
wins.y);
// Player 2 wins the current game
if (res == -1)
wins = new Point(wins.x,
wins.y + 1);
i = (i + 1) % n;
j = (j + 1) % m;
}
return wins;
}
// Driver code
public static void main(String[] args)
{
int k = 4;
String a = "SR", b = "R";
Point wins = countWins(k, a, b);
System.out.println(wins.x + " " + wins.y);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the above approach # Function that returns 1 if first # player wins, 0 in case of a draw # and -1 if second player wins def compare(first, second): # If both players have the same # move then it's a draw if (first == second): return 0 if (first == 'R'): if (second == 'S'): return 1 else: return -1 if (first == 'P'): if (second == 'R'): return 1 else: return -1 if (first == 'S'): if (second == 'P'): return 1 else: return -1 # Function that returns the count # of games won by both the players def countWins(k, a, b): n = len(a) m = len(b) i = 0 j = 0 # Total distinct games that # can be played moves = n * m wins = [ 0, 0 ] while (moves > 0): res = compare(a[i], b[j]) # Player 1 wins the current game if (res == 1): wins[0] += 1 # Player 2 wins the current game if (res == -1): wins[1] += 1 i = (i + 1) % n j = (j + 1) % m moves -= 1 # Number of times the above # n * m games repeat repeat = k // (n * m) # Update the games won wins[0] *= repeat wins[1] *= repeat # Remaining number of games after # removing repeated games rem = k % (n * m) while (rem > 0): res = compare(a[i], b[j]) # Player 1 wins the current game if (res == 1): wins[0] += 1 # Player 2 wins the current game if (res == -1): wins[1] += 1 i = (i + 1) % n j = (j + 1) % m return wins # Driver code if __name__ == "__main__": k = 4 a = "SR" b = "R" wins = countWins(k, a, b); print(wins[0], wins[1]) # This code is contributed by chitranayal
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that returns 1 if first player
// wins, 0 in case of a draw and -1 if
// second player wins
static int compare(char first, char second)
{
// If both players have the same
// move then it's a draw
if (first == second)
return 0;
if (first == 'R')
{
if (second == 'S')
return 1;
else
return -1;
}
if (first == 'P')
{
if (second == 'R')
return 1;
else
return -1;
}
if (first == 'S')
{
if (second == 'P')
return 1;
else
return -1;
}
return 0;
}
// Function that returns the count of games
// won by both the players
static Tuple<int, int> countWins(int k, string a,
string b)
{
int n = a.Length;
int m = b.Length;
int i = 0, j = 0;
// Total distinct games that
// can be played
int moves = n * m;
Tuple<int, int> wins = Tuple.Create(0, 0);
while (moves-- > 0)
{
int res = compare(a[i], b[j]);
// Player 1 wins the current game
if (res == 1)
wins = Tuple.Create(wins.Item1 + 1,
wins.Item2);
// Player 2 wins the current game
if (res == -1)
wins = Tuple.Create(wins.Item1,
wins.Item2 + 1);
i = (i + 1) % n;
j = (j + 1) % m;
}
// Number of times the above
// n * m games repeat
int repeat = k / (n * m);
// Update the games won
wins = Tuple.Create(wins.Item1 * repeat,
wins.Item2 * repeat);
// Remaining number of games after
// removing repeated games
int rem = k % (n * m);
while (rem-- > 0)
{
int res = compare(a[i], b[j]);
// Player 1 wins the current game
if (res == 1)
wins = Tuple.Create(wins.Item1 + 1,
wins.Item2);
// Player 2 wins the current game
if (res == -1)
wins = Tuple.Create(wins.Item1,
wins.Item2 + 1);
i = (i + 1) % n;
j = (j + 1) % m;
}
return wins;
}
// Driver Code
static void Main()
{
int k = 4;
string a = "SR", b = "R";
Tuple<int, int> wins = countWins(k, a, b);
Console.WriteLine(wins.Item1 + " " +
wins.Item2);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript implementation of the above approach
// Function that returns 1 if first player wins,
// 0 in case of a draw and -1 if second player wins
function compare(first,second)
{
// If both players have the same move
// then it's a draw
if (first == second)
return 0;
if (first == 'R')
{
if (second == 'S')
return 1;
else
return -1;
}
if (first == 'P')
{
if (second == 'R')
return 1;
else
return -1;
}
if (first == 'S')
{
if (second == 'P')
return 1;
else
return -1;
}
return 0;
}
// Function that returns the count of games
// won by both the players
function countWins(k,a,b)
{
let n = a.length;
let m = b.length;
let i = 0, j = 0;
// Total distinct games that
// can be played
let moves = n * m;
let wins = [0, 0];
while (moves-- > 0)
{
let res = compare(a[i],
b[j]);
// Player 1 wins the current game
if (res == 1)
wins = [wins[0] + 1,
wins[1]];
// Player 2 wins the current game
if (res == -1)
wins =[wins[0],
wins[1] + 1];
i = (i + 1) % n;
j = (j + 1) % m;
}
// Number of times the above
// n * m games repeat
let repeat = k / (n * m);
// Update the games won
wins = [wins[0] * repeat,
wins[1] * repeat];
// Remaining number of games after
// removing repeated games
let rem = k % (n * m);
while (rem-- > 0)
{
let res = compare(a[i],
b[j]);
// Player 1 wins the current game
if (res == 1)
wins = [wins[0] + 1,
wins[1]];
// Player 2 wins the current game
if (res == -1)
wins = [wins[0],
wins[1] + 1];
i = (i + 1) % n;
j = (j + 1) % m;
}
return wins;
}
// Driver code
let k = 4;
let a = "SR", b = "R";
let wins = countWins(k, a, b);
document.write(wins[0] + " " + wins[1]);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
0 2
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA