CodeForces - 626B Cards (全排列&模拟)

64bit IO Format: %I64d & %I64u

CodeForces - 626B

Cards

Submit Status

Description

Catherine has a deck of n

• 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.

Sample Input

Input

2RB

Output

G

Input

3GRG

Output

BR

Input

5BBBBB

Output

B

Hint

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.

//题意：

给你n个气球，这n个气球有三种颜色，蓝色（B），绿色（G），红色（R），现在玩一个游戏，每次从n个气球中拿出来两个，如果这两个气球颜色不同，那么这两个气球可以合并成一个第三种颜色的气球，如果这两个气球颜色相同，那么这两个气球可以合并成一个同种颜色的气球，问这样一直合并，直到最后一个。问最后能合并出哪几种颜色的气球。

//思路：

先将n个颜色不同的气球的颜色转换成数字，并将其存在一个数组a中，对a数组进行全排列，并对每一种情况进行合并，直到最后。（当合并出来的气球颜色已经等于3时，直接结束，节省时间，因为总共就3 种颜色）。

//HAIT：

首先得说一下输出格式，有的输入会对应多种输出，但要输出按字母升序排列（WA了3次）。。。

另外用我的思路写有一个bug，那就是当输入为（4     BGBG）时，我的输出是BG，但答案应该是BGR，在这块WA了8次。。。但加了一个特殊判断就过了^_^（在下面代码中会标注）。。。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
#define N 100010
#define M 1000000007
using namespace std;
char s[210];
int a[210];
int b[210];
int vis[5];
int c[5];
int d[5];
int chang(char c)
{
	if(c=='B') return 1;
	if(c=='G') return 2;
	if(c=='R') return 3;
}
void ch(int x)
{
	if(x==1) printf("B");
	else if(x==2) printf("G");
	else if(x==3) printf("R");
	
}
int main()
{
	int n,i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		memset(vis,0,sizeof(vis));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		memset(d,0,sizeof(d));
		scanf("%s",s);
		int kk=0;
		for(i=0;i<n;i++)
		{
			a[i]=chang(s[i]);
			if(!vis[a[i]])
			{
				vis[a[i]]=1;
				kk++;
			}	
			d[a[i]]++;
		}
		if((kk==2)&&(d[1]==2&&d[2]==2)||(d[1]==2&&d[3]==2)||(d[2]==2&&d[3]==2))//加一个特殊判断 
		{
			printf("BGR\n");
			continue;
		}
		sort(a,a+n);
		int k=0;
		memset(vis,0,sizeof(vis));
		do
		{
			for(i=0;i<n;i++)
				b[i]=a[i];
//			for(i=0;i<n;i++)
//				printf("%d ",b[i]);
//			printf("\n");
			for(i=1;i<n;i++)
			{
				if(b[i]==b[i-1])
					b[i]=b[i-1];
				else
				{
					b[i]=(b[i]+b[i-1])%4;
					if(!b[i])
						b[i]=2;
				}
			}
//			printf("%d\n",b[n-1]);
			if(!vis[b[n-1]])
			{
				vis[b[n-1]]=1;
				c[k++]=b[n-1];
			}
			if(k==3)
				break;		
		}while(next_permutation(a,a+n));
		sort(c,c+k);
		for(i=0;i<k;i++)
			ch(c[i]);
		printf("\n");
	}
	return 0;
}