Explanation:
To win the game, Chef needs to score more than ⌊N/2⌋ (i.e. W = N/2+1) points. It doesn’t matter if Chef loses or draws D = N - (N/2+1) rounds.
Among the characters ‘R’, ‘P’ and ‘S’, ‘P’ is lexicographically smallest.
To find the lexicographically smallest sequence of moves, Chef will play ‘P’ move D times from the beginning of the game. Each time when Chef loses or draws playing move ‘P’, D will be decreased by 1. When D becomes 0 proceeding in this fashion, then Chef will play the winning moves (i.e. ‘R’ against ‘S’, ‘P’ against ‘R’ and ‘S’ against ‘P’).
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t; cin>>t;
while(t--)
{
int n; cin>>n;
string a; cin>>a;
string b;
int w = n/2 + 1; // win
int d = n - w; // lose/draw
for(int i=0; i<n; i++)
{
if(d != 0)
{
b.push_back('P');
if(a[i] != 'R')
d--;
}
else
{
if(a[i] == 'R')
b.push_back('P');
else if(a[i] == 'P')
b.push_back('S');
else
b.push_back('R');
}
}
cout<<b<<endl;
}
return 0;
}