POJ 3087 Shuffle'm Upシミュレーション
标题:シャッフルを繰り返す.与えられたシーケンスを得るために必要なステップ数を求める.所望のシーケンスを得ることができなければ、-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;
}