SRM 641 Div1 Medium ShufflingCardsDiv1

最終状態から、初期状態に戻していく方針で考察していく。

まず、0回のシャッフルで良い場合は 0 を返す。
それ以外の場合は、
0-origin で偶数番目のカードについて、初期状態で先頭 N 枚に来るカード (すなわち N 以下の数が書かれたのカード) の枚数を X とする。
手で考察すると、以下のような結果が得られる。

1 回のシャッフルで X = N になる。
2 回のシャッフルで X = ceil((N+1)/2) になる。
N が偶数のときは、3回のシャッフルで X は任意の整数にできる。
N が奇数のときは、3回のシャッフルで X は 1 以上の整数にでき、4回のシャッフルで X は任意の整数にできる。

class ShufflingCardsDiv1 {
	public:
	int shuffle(vector <int> a) {
		int n = a.size();
		bool ok = true;
		rep(i, n) if(a[i]!=i+1) ok = false;
		if(ok) return 0;
		int cnt = 0;
		rep(i, n/2) if(a[i*2]<=n/2) cnt++;
		if(cnt==n/2) return 1;
		if(cnt==(n/2+1)/2) return 2;
		if(n/2%2==0 || cnt>0) return 3;
		return 4;
	}
};