CodeForces 626B-Cards【DFS】

我就是我 2022-08-21 00:07 96阅读 0赞

B. Cards

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Input

3
    GRG

Output

Input

5
    BBBBB

Output

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.

解题思路：

题目大意就是，给出一个字符串的长度和这个字符串，这个字符串只有BGR这三个字母组成，他们合并的规则是两个不同的可以合成第三个，两个相同的可以合成一个它本身，并且可以不按照相邻或不相邻。

很明显一个字符串合并到最后都能得到一个字符，我们要做的就是输出BGR所有的情况，按字典序排列。

既然可以不相邻所以我们就统计数量就行。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n;
    int g,r,b;
    bool vis[200][200][200];
    int x1,x2,x3;
    void DFS(int bb,int gg,int rr)
    {
    	if(bb==0&&gg==0&&rr==1)
    	{
    		if(x3==0)
    		x3=1;
    		return ;
    	}
    	if(bb==1&&gg==0&&rr==0)
    	{
    		if(x1==0)
    		x1=1;
    		return ;
    	}
    	if(bb==0&&gg==1&&rr==0)
    	{
    		if(x2==0)
    		x2=1;
    		return ;
    	}
    	if(bb>0&&gg>0&&!vis[bb-1][gg-1][rr+1])
    	{
    		vis[bb-1][gg-1][rr+1]=true;
    		DFS(bb-1,gg-1,rr+1);
    	}
    	if(bb>0&&rr>0&&!vis[bb-1][gg+1][rr-1])
    	{
    		vis[bb-1][gg+1][rr-1]=true;
    		DFS(bb-1,gg+1,rr-1);
    	}
    	if(rr>0&&gg>0&&!vis[bb+1][gg-1][rr-1])
    	{
    		vis[bb+1][gg-1][rr-1]=true;
    		DFS(bb+1,gg-1,rr-1);
    	}
    	if(bb>1&&!vis[bb-1][gg][rr])
    	{
    		vis[bb-1][gg][rr]=true;
    		DFS(bb-1,gg,rr);
    	}
    	if(gg>1&&!vis[bb][gg-1][rr])
    	{
    		vis[bb][gg-1][rr]=true;
    		DFS(bb,gg-1,rr);
    	}
    	if(rr>1&&!vis[bb][gg][rr-1])
    	{
    		vis[bb][gg][rr-1]=true;
    		DFS(bb,gg,rr-1);
    	}
    }
    int main()
    {
    	char map[2000];
    	while(scanf("%d",&n)!=EOF)
    	{
    		g=r=b=0;
    		int ll;
    		scanf("%s",map);
    		int i,j;
    		for(i=0;i<n;i++)
    		{
    			if(map[i]=='G')
    			{
    				g++;
    			}
    			else if(map[i]=='B')
    			{
    				b++;
    			}
    			else
    			{
    				r++;
    			}
    		}
    		x1=0,x2=0,x3=0;
    		memset(vis,false,sizeof(vis));
    		DFS(b,g,r);
    		if(x1)
    		printf("B");
    		if(x2)
    		printf("G");
    		if(x3)
    		printf("R");
    		printf("\n");
    	}
    	return 0;
    }