Spider Man [Codeforces 366 : Div.2 B]

問題

http://codeforces.com/contest/705/problem/B

n個の数列 ai が与えられる。
n個のクエリについて答える。
各i番目のクエリで以下のゲームを行う。

1. 場に a0 ～ ai があり、1さんが先手
2. 自分の番が来たら、場にある数のうち1つを2つの数に分割する
3. もし、分割できる数が無い(全部1)なら負け

このルールの時、どちらが勝つかを各クエリ答える

1 <= n <= 10^5
1 <= ai <= 10^9

考察

1. クエリをO(1)かO(log n)で捌ければOK
2. 順番に数を増やしていくので、前の結果が使えれば良さそう
3. こういう問題によくある「最適に行動した時」が無い
4. どうプレイしても結果が同じになる？

5. 実験してみる

2 -> 1,1
3 -> 1,2 -> 1,1,1
4 -> 1,3 or 2,2 -> 1,1,2 -> 1,1,1,1
5 -> 1,4 or 2,3 -> 1,1,3 or 1,2,2 -> 1,1,1,2 -> 1,1,1,1,1

6. ある数 x の分割回数は x-1 回になる

7. 分割回数の総和が奇数なら"1"の勝ち、偶数なら"2"の勝ち

実装

http://codeforces.com/contest/705/submission/19711325

typedef long long ll;
int n;
//-----------------------------------------------------------------
int main() {
	cin >> n;
	
	ll sm = 0;
	rep(i, 0, n) {
		int a;
		scanf("%d", &a);
		sm += a - 1;
		sm %= 2;
		if (sm == 0)
			printf("2\n");
		else
			printf("1\n");
	}
}