POJ 3087 Shuffle'm Upシミュレーション

1038 ワード

标题:シャッフルを繰り返す.与えられたシーケンスを得るために必要なステップ数を求める.所望のシーケンスを得ることができなければ、-1を出力する.問題:あるステップで得られたシーケンスが初期シーケンスと同じである場合、所与のターゲットシーケンスが得られないと判断できます.
#include <iostream>
using namespace std;

char s1[101], s2[101], shuffle[201], start[201], goal[201];

int solve( int c )
{
	int x, y, i, step = 0;
	while ( 1 )
	{
		step++;
		x = y = 0;
		for ( i = 0; i < 2 * c; i++ )
		{
			if ( i % 2 == 0 )
				shuffle[i] = s2[x++];
			else
				shuffle[i] = s1[y++];
		}

		shuffle[i] = '\0';
		if ( strcmp(shuffle,goal) == 0 )
			return step;
		if ( strcmp(shuffle,start) == 0 )
			return -1;

		strncpy ( s1, shuffle, c );
		s1[c] = '\0';
		strncpy ( s2, shuffle + c, c );
		s2[c] = '\0';
	} 
}

int main()
{
	int n, c, t = 0;
	scanf("%d",&n);
	while ( n-- )
	{
		scanf("%d",&c);
		scanf("%s%s%s",s1, s2, goal);
		strncpy ( start, s1, c );
		strncpy ( start + c, s2, c );
		start[2*c] = '\0';
		printf("%d %d
", ++t, solve(c)); } return 0; }