There are NN players standing in a line, indexed 11 to NN 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 SS of length NN, i.e,
- SiSi is equal to RR if player ii will play Rock.
- SiSi is equal to PP if player ii will play Paper.
- SiSi is equal to SS if player ii will play Scissors.
Let W(i,j)W(i,j) denote the move played by the winner if players i,i+1,…,ji,i+1,…,j compete in order from left to right. That is,
- First, players ii and i+1i+1 play a game
- The winner of this game plays against player i+2i+2
- The winner of the second game plays against player i+3i+3
- The winner of the first j−i−1j−i−1 games plays against player jj, and the move played by the winner of this game is declared to be W(i,j)W(i,j).
If i=ji=j, then player ii is considered to be the winner and W(i,i)=SiW(i,i)=Si.
Your task is to find the value of W(i,N)W(i,N) for all ii from 11 to NN.
Note : If a person with index ii and index jj (i<ji<j) play against each other, then:
- If Si≠SjSi≠Sj, the winner is decided by classical rules, i.e, rock beats scissors, scissors beats paper, and paper beats rock.
- If Si=SjSi=Sj, the player with lower index (in this case, ii) wins.
- The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN, the number of players.
- The second line of each test case contains the string SS of length NN, denoting the moves chosen by the players.
For each test case, print a single line containing a string of length NN, whose ii-th character is W(i,N)W(i,N).
- SiSi is either RR, PP or SS
- Sum of NN over all test cases doesn’t exceed 5⋅1055⋅105
Subtask 1 (10 points):
- Sum of NN over all test cases doesn’t exceed 50005000
Subtask 1 (90 points):
- Original constraints
Sample Input 1
2 1 S 4 SSPR
Sample Output 1
Test Case 1. W(1,1)=SW(1,1)=S as there is only one player.
Test Case 2.
For W(1,4)W(1,4) the game is played as follows :
- Player 11 and 22 compete, player 11 wins.
- Player 11 and 33 compete, player 11 wins.
- Player 11 and 44 compete, player 44 wins.
Hence, we print W(1,4)=S4=RW(1,4)=S4=R
For W(3,4)W(3,4) the game is played as follows :
- Player 33 and 44 compete, player 33 wins.
Hence, we print W(3,4)=S3=P
Will be updated today.
Refer and Earn Rs. 1200 per referral on Upstox
Click here to know more
- Pyramid Traversal Solution | DEC LONG CHALLENGE | Codechef
- Increasing String Solution | DEC LONG CHALLENGE | Codechef
- Squares Counting Solution | DEC LONG CHALLENGE | Codechef
- Rock Paper Scissors Solution | DEC LONG CHALLENGE | Codechef
- Check Mate Solution | DEC LONG CHALLENGE | Codechef