Bubble Cup 8 Final : D. Tablecity

なんか変な問題。
http://codeforces.com/contest/575/problem/D

問題

縦２行横1000列のグリッドがある。
敵はいずれかのマス(X,Y)におり、１ターン毎に(X-1,Y-1),(X-1,Y),(X-1,Y+1),(X+1,Y-1),(X+1,Y),(X+1,Y+1)のどこかに移動する。

プレイヤーは１ターンで２マスを調査することができる。
そこに敵がいたらプレイヤーの勝ちである。

初期に敵がどこにいて、以後どう動いても2015ターン以内に敵を見つける調査順を答えよ。

解法

Y方向は無視して考える。
敵はX座標が奇数・偶数交互に来るように動く。

そこで最初にX座標が1～1000を順に調べ、次に2～1000を順に調べればよい。
初期位置が奇数の場合前半、偶数の場合後半のどこかで必ず引っかかる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	_P("%d\n",1999);
	FOR(i,1000) _P("%d %d %d %d\n",i+1,1,i+1,2);
	FOR(i,999) _P("%d %d %d %d\n",i+2,1,i+2,2);
}

まとめ

高さを２段にしたのはなんでだろうね。