3087 Shuffle'm Up

問題概要

チップの山S1,S2を、S2の最も下のチップを取り、新たな山S12に置く。
S1の最も下のチップを取り、S12の一番上に置く。
S2の最も下のチップを……と繰り返して山S12を作る。

山S12が目標の配列ならばシャッフルは終了で、そうでないならS12の下半分を新たなS1,上半分を新たなS2として同じ操作を繰り返す。

最初のS1,S2が与えられたとき、目標の配列を得るまでにかかるシャッフルの回数を求めよ。
ただし、山は下のチップから順に与えられる。

チップの枚数は1000以下である。

解法

山は下にあるチップが先頭になるとかいう罠が。

問題文で言われた通りのシャッフルを愚直にシミュレートして間に合う。
シャッフル後、今までと同じ配列に戻ったらループしているので-1を出力。

ソースコード

int main()
{
	int n,T,ans; cin>>T;
	rep(U,T){
		string s,t,g;
		cin>>n>>s>>t>>g;
		set<string> S;
		
		ans=1;
		for(;;ans++){
			string u(2*n,' ');
			rep(i,n)u[i*2]=t[i],u[i*2+1]=s[i];
			if(u==g)break;
			if(S.count(u)){
				ans=-1; break;
			}
			S.insert(u);
			t=u.substr(n); s=u.substr(0,n);
		}
		cout<<U+1<<" "<<ans<<endl;
	}
	return 0;
}