URAL 1501 Sense of Beauty

1501. Sense of Beauty

Time limit: 0.5 second
Memory limit: 64 MB
The owner of a casino for New Russians has a very refined sense of beauty. For example, after a game there remain two piles with the same number of cards on the table, and the owner likes the cards to be arranged into two piles according to the color: one pile with red cards and the other with black cards. Of course, this is done not by the owner himself, but by a croupier. The owner just likes to watch the process. The croupier takes a card from the top of one of the initial piles and puts it into one of the new piles; this is repeated until all the cards from the initial piles are transferred. The owner doesn't like it if one of the resulting piles grows faster than the other. At each moment the resulting piles must not differ in size by more than one card; a bigger difference would contradict the owner's sense of beauty. Help the croupier to arrange the cards according to the tastes of his owner.

Input

The first line of the input contains the number 
N of cards in each of the piles (4 ≤ 
N ≤ 1000). Each of the next two lines contains 
N digits 0 or 1 describing the piles: 1 denotes a red-suit card and 0 denotes a black-suit card. The cards in a pile are described from the top to the bottom. There are in total 
N red and 
N black cards in the two piles.

Output

Output a line containing 2
N digits 1 or 2, which describes the process of transferring the cards. Each number shows the number of the pile from which a card is taken. If it is impossible to perform this task according to the given rules, output "Impossible".

Samples

input
output

4
0011
0110

22121112

4
1100
1100

Impossible

제목:
카드 두 무더기를 줄게, 카드 색깔은 빨간색이나 검은색밖에 없어.그리고 두 무더기의 카드 꼭대기에서 카드를 뽑습니다. 매번 뽑을 때마다 두 무더기 중의 한 무더기를 선택할 수 있습니다.매번 추첨이 끝나면 얻은 패, 레드카드와 블랙카드의 수량 차이는 반드시 1을 넘지 않아야 한다.
방법:
모두 1000장씩 있기 때문에 dp기억화 검색이 가능합니다.pp[i][j]대표는 첫 번째 카드에서 i장을 뽑았고, 두 번째 카드에서 j장을 뽑은 경우 규칙을 어기지 않고 이 상태에 도달하는 방법이 있습니까?만약에 dp[i][j]가 있다면 0, 1, 2, 0은 현재 블랙카드가 하나 더 있다는 것을 의미하고, 1은 현재 레드카드가 똑같이 많다는 것을 의미하며, 2는 현재 레드카드가 한 장 더 많다는 것을 의미한다.2 이런 상태에 이르지 못한 방법을 나타낸다.
그 다음에 몇 가지 옮기는 방법은 모두 dfs(i-1, j) 또는 dfs(j, i-1)가 도달할 수 있는 상황에서만 옮길 수 있다.

int dp[1100][1100];//
int n;

int num1[1100];
int num2[1100];

int bu[1100];
int dfs(int i,int j)
{
	if(~dp[i][j])//  -1，        ，      ，     
		return dp[i][j];
	if(i==0&&j==0)
		return dp[i][j]=1;//0 0  1   2 1 


	if(i!=0)
	{ 
		if(dfs(i-1,j)==0&&num1[i]==1)//    ，              ，             
		{
			bu[i+j]=1;
			return dp[i][j]=1;
		}	
		if(dfs(i-1,j)==1)
		{
			if(num1[i]==1)
			{
				bu[i+j]=1;
				return dp[i][j]=2;
			}
			if(num1[i]==0)
			{
				bu[i+j]=1;
				return dp[i][j]=0;
			}
		}

		if(dfs(i-1,j)==2&&num1[i]==0)
		{
			bu[i+j]=1;
			return dp[i][j]=1;
		}
	}
	if(j!=0)
	{
		if(dfs(i,j-1)==0&&num2[j]==1)
		{
			bu[i+j]=2;
			return dp[i][j]=1;
		}

		if(dfs(i,j-1)==1)
		{
			if(num2[j]==1)
			{
				bu[i+j]=2;
				return dp[i][j]=2;
			}
			if(num2[j]==0)
			{
				bu[i+j]=2;
				return dp[i][j]=0;
			}
		}

		if(dfs(i,j-1)==2&&num2[j]==0)
		{
			bu[i+j]=2;
			return dp[i][j]=1;
		}
	}
	return dp[i][j]=-2;
}
char n1[1100];
char n2[1100];
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%s%s",n1,n2);
		memset(dp,-1,sizeof dp);
		for(int i=1;i<=n;i++)
		{
			num1[i]=n1[i-1]-'0';
			num2[i]=n2[i-1]-'0';
		}

		if(dfs(n,n)!=-2)
		{
			for(int i=1;i<=2*n;i++)
				printf("%d",bu[i]);

			puts("");
		}
		else
			puts("Impossible");

	}
	return 0;
}