Bubble Cup8 Finals D. Tablecity

問題

概要

2行1000列のグリッドがある.このグリッドのどこかに泥棒がいる.

泥棒の初期位置は分からないが,2015ターン以内にこの泥棒を捕まえたい.

1ターンごとに泥棒は,右上,右,右下,左上,左,左下のどこかのマスに移動する.

1ターンごとに,ある2つのマスを指定できる.指定したマスに泥棒がいれば勝ちである.

解法

逃げられないようにするには2行どちらも抑える必要がある.
次に1ターンごとに泥棒のx座標は必ず1変化する.
すると,1,2,3,…..1000と見たあと,1000,999,….,1と見ると,必ず捕まえることができる.

簡単な証明:
泥棒の初期x座標が奇数のとき,1手ごとに泥棒との距離は2小さくなるか,変化しないかのどちらか.1000手以内に距離が必ず0になる.

泥棒の初期x座標が偶数のとき,1手ごとに泥棒との距離は2小さくなるか,変化しないかのどちらか.最初の1000手では捕まらないが,残りの1000手のどこかで距離が必ず0になる.

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
public class Solver
{
public void Solve()
{

IO.Printer.Out.WriteLine(2000);
for (int i = 1; i <= 1000; i++)
IO.Printer.Out.WriteLine("{0} 1 {1} 2", i, i);
for (int i = 1000; i >= 1; i--)
IO.Printer.Out.WriteLine("{0} 1 {1} 2", i, i);
}
}

まとめ

output onlyのパズルのような問題.面白かった.