Rock Paper Scissors ROPASCI Solution
There are N players standing in a line, indexed 1 to N from left to right. They all play a game of Rock, Paper, Scissors. Each player has already decided which move they want to play. You are given this information as a string S of length N, i.e
- Si is equal to R if player ii will play Rock.
- Si is equal to P if player ii will play Paper.
- Si is equal to S if player ii will play Scissors.
Let W(i,j) denote the move played by the winner if players i,i+1,…,j compete in order from left to right. That is,
- First, players ii and i+1 play a game
- The winner of this game plays against player i+2
- The winner of the second game plays against player i+3
- The winner of the first j−i−1 games plays against player j, and the move played by the winner of this game is declared to be W(i,j).
If i=j, then player ii is considered to be the winner and W(i,i)=Si.
Your task is to find the value of W(i,N) for all ii from 1 to N.
Note : If a person with index ii and index j (i<j) play against each other, then:
- If Si≠Sj, the winner is decided by classical rules, i.e, rock beats scissors, scissors beats paper, and paper beats rock.
- If Si=Sj, the player with lower index (in this case, i) wins.
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N, the number of players.
- The second line of each test case contains the string S of length N, denoting the moves chosen by the players.
Output Format
For each test case, print a single line containing a string of length N, whose i-th character is W(i,N).
Constraints
- 1≤T≤105
- 1≤N≤5⋅105
- Si is either R, P or S
- Sum of N over all test cases doesn’t exceed 5⋅105
Subtasks
Subtask 1 (10 points):
- 1≤T≤1000
- 1≤N≤5000
- Sum of N over all test cases doesn’t exceed 5000
Subtask 1 (90 points):
- Original constraints
Sample Input 1
2
1
S
4
SSPR
Sample Output 1
S
RRPR
Explanation
Test Case 1. W(1,1)=S as there is only one player.
Test Case 2. For W(1,4) the game is played as follows :
- Player 1 and 2 compete, player 1 wins.
- Player 1 and 3 compete, player 1 wins.
- Player 1 and 4 compete, player 4 wins.
Hence, we print W(1,4)=S4=R
For W(3,4) the game is played as follows :
- Player 3 and 4 compete, player 3 wins.
Hence, we print W(3,4)=S3=P
SOLUTION
Program Python: Rock Paper Scissors ROPASCI Solution in Python
# cook your dish here
def match(a,b):
if a==b:
return a
if a == 'S' and b == 'R' or a == 'R' and b == 'S':
return 'R'
elif a == 'S' and b == 'P' or a == 'P' and b == 'S':
return 'S'
elif a == 'P' and b == 'R' or a == 'R' and b == 'P':
return 'P'
else:
return None
for _ in range(int(input())):
n = int(input())
s = input()
dp_r = [None]*(n+1)
dp_p = [None]*(n+1)
dp_s = [None]*(n+1)
ans = [None]*(n+1)
#base case
ans[n] = s[n-1]
dp_r[n] = match('R', s[n-1])
dp_p[n] = match('P', s[n-1])
dp_s[n] = match('S', s[n-1])
for i in range(n-1,1-1,-1):
#find dp_arrays and ans
#dp_r
r_res = match('R', s[i-1])
if r_res == 'R':
dp_r[i] = dp_r[i+1]
elif r_res == 'P':
dp_r[i] = dp_p[i+1]
elif r_res == 'S':
dp_r[i] = dp_s[i+1]
#dp_p
p_res = match('P', s[i-1])
if p_res == 'R':
dp_p[i] = dp_r[i+1]
elif p_res == 'P':
dp_p[i] = dp_p[i+1]
elif p_res == 'S':
dp_p[i] = dp_s[i+1]
#dp_s
s_res = match('S', s[i-1])
if s_res == 'R':
dp_s[i] = dp_r[i+1]
elif s_res == 'P':
dp_s[i] = dp_p[i+1]
elif s_res == 'S':
dp_s[i] = dp_s[i+1]
#ans
if s[i-1] == 'R':
ans[i] = dp_r[i+1]
elif s[i-1] == 'P':
ans[i] = dp_p[i+1]
elif s[i-1] == 'S':
ans[i] = dp_s[i+1]
print(''.join(ans[1:]))
Program C++: Rock Paper Scissors ROPASCI Solution in C++
#include <iostream>
#include<cassert>
#include<vector>
#include<string>
using namespace std;
char match(char a, char b)
{
if(a==b) return a;
else if(a=='R' && b=='P' || a=='P' && b=='R')
{
return 'P';
}
else if(a=='R' && b=='S' || a=='S' && b=='R')
{
return 'R';
}
else if(a=='P' && b=='S' || a=='S' && b=='P')
{
return 'S';
}
else
{
assert (false);
}
}
int main() {
// your code goes here
int t;
cin>> t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
vector<char> dp_r(n+1);
vector<char> dp_p(n+1);
vector<char> dp_s(n+1);
vector<char> ans(n+1);
ans[n]=s[n-1];
dp_r[n]=match('R', s[n-1]);
dp_p[n]=match('P', s[n-1]);
dp_s[n]=match('S', s[n-1]);
for(int i =n-1;i>=1;i--)
{
char r_res = match('R', s[i-1]);
if(r_res=='R')
{
dp_r[i]= dp_r[i+1];
}
else if(r_res=='P')
{
dp_r[i]= dp_p[i+1];
}
else if(r_res=='S')
{
dp_r[i]= dp_s[i+1];
}
char p_res = match('P', s[i-1]);
if(p_res=='R')
{
dp_p[i]= dp_r[i+1];
}
else if(p_res=='P')
{
dp_p[i]= dp_p[i+1];
}
else if(p_res=='S')
{
dp_p[i]= dp_s[i+1];
}
char s_res = match('S', s[i-1]);
if(s_res=='R')
{
dp_s[i]= dp_r[i+1];
}
else if(s_res=='P')
{
dp_s[i]= dp_p[i+1];
}
else if(s_res=='S')
{
dp_s[i]= dp_s[i+1];
}
if(s[i-1] == 'R')
{
ans[i]=dp_r[i+1];
}
else if(s[i-1] == 'P')
{
ans[i]=dp_p[i+1];
}
else if(s[i-1] == 'S')
{
ans[i]=dp_s[i+1];
}
}
for(int i =1; i<=n;i++)
{
cout<<ans[i];
}
cout<<endl ;
}
}
December Long Challenge 2021 Solution
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef