Cards
Catherine has a deck of n cards, each of which is either red, green, or blue. As long as there are at least two cards left, she can do one of two actions:
- take any two (not necessarily adjacent) cards with different colors and exchange them for a new card of the third color;
- take any two (not necessarily adjacent) cards with the same color and exchange them for a new card with that color.
She repeats this process until there is only one card left. What are the possible colors for the final card?
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 200) — the total number of cards.
The next line contains a string s of length n — the colors of the cards. s contains only the characters 'B', 'G', and 'R', representing blue, green, and red, respectively.
Output
Print a single string of up to three characters — the possible colors of the final card (using the same symbols as the input) in alphabetical order.
Examples
input
2 RB
output
G
input
3 GRG
output
BR
input
5 BBBBB
output
B
Note
In the first sample, Catherine has one red card and one blue card, which she must exchange for a green card.
In the second sample, Catherine has two green cards and one red card. She has two options: she can exchange the two green cards for a green card, then exchange the new green card and the red card for a blue card. Alternatively, she can exchange a green and a red card for a blue card, then exchange the blue card and remaining green card for a red card.
In the third sample, Catherine only has blue cards, so she can only exchange them for more blue cards.
------------------------------------------editorial----------------------------
we can solve this problem in many ways , there are some good implementation solution also of this problem , but we can write a dp solution also , dp[r][g][b] if pre computed than dont let it repeat
----------------------code-------------------------------------------------
/* ------------------------------ header -------------------------------------- */
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
//typedef long int li;
typedef unsigned long long int ulli;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define test() int t; cin>>t;while(t--)
#define si(x) scanf("%d",&x)
#define slli(x) scanf("%lld",&x)
#define sli(x) scanf("%ld",&x)
#define sd(x) scanf("%d",&x)
#define pfi(x) printf("%d\n",x)
#define pfli(x) printf("%ld\n",x)
#define pflli(x) printf("%lld\n",x)
#define abs(x) ((x)>0?(x):-(x))
#define TRI(a,b,c) mp(mp(a,b),c)
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define all(x) x.begin(),x.end()
#define sz size()
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repl(i,a,b) for(lli i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define foreach( gg,itit ) for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
typedef pair<lli,lli> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
/* ------------------------------ header end -------------------------------------- */
/*---------------------------------------- storage start ---------------------------------------*/
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
lli comb[1001][1001];
int vis[1000000];
list<int> li[1000000];
/*---------------------------------------- storage end ---------------------------------------*/
/*------------------------------------------ functions start ------------------------------------*/
lli gcd(lli a, lli b){ if(b)return gcd(b,a%b); return a;}
inline void add(int &x, int y){x+=y; if(x>=mod)x-=mod; if(x<0)x+=mod;} // (a+b)%mod;
lli mulmod ( lli a , lli b,lli mod_val) // (a*b)%c for large values of a and b
{
lli ret = 0;
while(b)
{
if(b&1)
{
ret += a;
if(ret >= mod_val)
ret %= mod_val;
}
a = a + a;
if(a >= mod_val) a %= mod_val;
b >>= 1;
}
return ret;
}
long long int read_int()
{
char r;
bool start=false,neg=false;
long long int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
/*inline void printint( long n)
{
if(n == 0)
{
putchar_unlocked('0');
putchar_unlocked('\n');
}
else if(n == -1)
{
putchar_unlocked('-');
putchar_unlocked('1');
putchar_unlocked('\n');
}
else
{
char buf[11];
buf[10] = '\n';
int i = 9;
while(n)
{
buf[i--] = n % 10 + '0';
n /= 10;
}
while(buf[i] != '\n')
putchar_unlocked(buf[++i]);
}
} */
lli combination()
{
for(int i = 0; i < 1000; i++) {
comb[i][0] = 1;
for(int j = 1; j <= i; j++)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
}
}
#define pp pair<pair<int,int>,int>
bool compare(pp p1,pp p2)
{
if(p1.first.first<p2.first.first)return true;
else if(p1.first.first>p2.first.first) return false;
else
{
if(p1.first.second>p2.first.second) return true;
else return false;
}
}
int dfs(int index)
{
stack<int> s; s.push(index); vis[index]=1;
while(!s.empty())
{
int index=s.top(); s.pop();
list<int> :: iterator it;
for(it=li[index].begin();it!=li[index].end();it++)
{
if(!vis[*it] )
{
vis[*it]=1; s.push(*it);
}
}
}
}
/*------------------------------------------ functions end ------------------------------------*/
/*
void bfs()
{
}
void lps()
{
}
mst
seg tree
*/
/*---------------------------------------- main ------------------------------------*/
int fr=0,fg=0,fb=0;
int dp[210][210][210];
int solve(int r,int g,int b)
{
if(r<0 || b<0 || g<0) return 0;
else if(fr==1 && fb==1 && fg==1) return 0;
else if(dp[r][g][b]!=-1)return 0;
else if(r==1 && g==0 && b==0)
{
fr=1;
return 0;
}
else if(r==0 && g==1 && b==0)
{
fg=1;
return 0;
}
else if(r==0 && g==0 && b==1)
{
fb=1;
return 0;
}
else
{
dp[r][g][b]=1;
if(r>=2)
solve(r-1,g,b);
if(g>=2)
solve(r,g-1,b);
if(b>=2)
solve(r,g,b-1);
solve(r-1,g-1,b+1);
solve(r-1,g+1,b-1);
solve(r+1,g-1,b-1);
}
}
int main()
{
//freopen("abc.txt","r",stdin);
//freopen("pqr.txt","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);
memset(dp,-1,sizeof dp);
int n;
cin>>n;
string s;
cin>>s;
int len=s.length();
int r=0,g=0,b=0;
for(int i=0;i<len;i++)
{
if(s[i]=='R') r++;
else if(s[i]=='G') g++;
else if(s[i]=='B') b++;
}
solve(r,g,b);
if(fb==1) cout<<"B";
if(fg==1) cout<<"G";
if(fr==1) cout<<"R";
}
No comments:
Post a Comment