問題文

この問題は interactive である．採点用プログラムが最大で 実行時間 100 ms / メモリ 8 MB 程度を使用する．

横 500 px，縦 500 px のキャンバスがあり，画素の位置は整数の組 (x, y) (0 \leq x < 500，0 \leq y < 500) で表される．x 座標が増える方向が左から右へ，y 座標が増える方向が上から下であることに注意せよ．各画素は白か黒かのいずれかである．はじめ，キャンバスのどの画素も白である．

いま，きつね 0 ときつね 1 がともに巨大な鉛筆を抱えた状態で画素 (0, 0) にいる．以下の操作を高々 10\,000 回行うことで，与えられる目標のデザインに沿った画像を作り上げたい．

• 操作: 画素 (x, y) を指定し，「きつねさんは画素 (x, y) へ移動してください」と声をかける．すると，きつね 0 ときつね 1 のうち等確率でランダムに選ばれた一方が画素 (x, y) へ移動する．すでに (一方または双方の) きつねがいる画素を指定して操作を行っても構わない．

きつねは移動するときに，移動前の画素から移動後の画素へと黒い線分を引く．厳密には，ブレゼンハムのアルゴリズムによって線分の通る画素を求め，そのすべての画素を黒へと変える．(詳細は配布されるローカル用テスターの実装も参考にせよ)

今年の看板のデザイン

達成条件

目標のデザインは横 500 px，縦 500 px の白黒画像として与えられる．操作によって作られた画像が以下の 2 条件をどちらも満たしていれば「デザインに沿った」とみなされる：

• 目標のデザインにおいて黒であるような画素のうち，作られた画像においても黒であるような画素の割合が 85% 以上であること．
• 目標のデザインにおいて白であるような画素のうち，作られた画像においても白であるような画素の割合が 70% 以上であること．

データ

この問題を解くために必要なデータをまとめた zip ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．

• atrandom/input.png: 目標デザインを表す画像．画像サイズは横 500 px，縦 500 px である．
• atrandom/input.txt: 目標デザインを下記の入出力の仕様に合わせてテキストファイル化したもの．実際の採点時に提出されたプログラムに最初に与えられる入力と同一である．
• atrandom/interactive_tester.py: この問題における interactive なやりとりをローカルでテストするための Python 3 製ツール．
  • python3 interactive_tester.py <input_file> <seed> -- <cmd_line_solution> として使用する．
    • <input_file> は目標デザインをテキスト化したもののファイルパス．実際の採点と同様のケースでテストするには，同梱されている input.txt を指定すればよい．
    • <seed> は移動するきつねを決める際に用いられる乱数のシード．本ツールで用いられている乱数生成方法は実際の採点時に用いられるものとは必ずしも一致しない．
    • <cmd_line_solution> はあなたの提出するプログラムを実行するためのコマンドを表す文字列．
  • たとえば C++ で書かれた解答を本ツールと同じディレクトリでコンパイルして solver.out という実行可能ファイルを作った場合，python3 interactive_tester.py input.txt 0 -- ./solver.out などとして実行できる．
  • 同様にたとえば Python で書かれた solver.py という解答を本ツールと同じディレクトリに置いた場合，python3 interactive_tester.py input.txt 0 -- python solver.py などとして実行できる．
  • なお，このツール内にある drawline 関数はブレゼンハムのアルゴリズムを実装したものとなっている．解答の作成時などに参考にしてもよい．
• atrandom/visualize.html: ローカル用のテストツールが出力した詳細な画像データを見るためのビジュアライザ．
  • ローカル用テストツールが正しく実行されると，interactive_tester.dump というファイルが同じ階層に生成される．このファイルをビジュアライザに与えることで，あなたのプログラムが作った画像を可視化し，画像として保存することができる．

入出力

1. 整数 W,H,T が空白区切りで標準入力に与えられる．
   • これは目標のデザインおよびキャンバスが横 W px，縦 H px からなり，高々 T 回の操作を行ってよいことを表す．
   • すなわち，この問題の入力においては W = 500，H = 500，T = 10\,000 を満たす．
2. . および # のみからなる W 文字の文字列が H 行にわたって標準入力に与えられる．
   • このうち y 行目 (0 \leq y < H) の文字列の x 文字目 (0 \leq x < W) は，目標のデザインにおける画素 (x, y) の色を表す．白は .，黒は # によって表される．
3. 以下を (最大で) T 回繰り返す．
   1. あなたのプログラムは 2 つの整数 x, y を空白区切りで標準出力に出力しなければならない．
      • (x, y) = (-1, -1) のとき，これ以上操作を行わないことを示し，繰り返しを終了する．これ以降，入力が与えられることはない．
      • そうでないとき，0 \leq x < W かつ 0 \leq y < H でなければならず，画素 (x, y) を指定して操作を行うことを示す．
   2. 操作の結果，きつね k (k = 0, 1) が動いたとすると，整数 k が標準入力に与えられる．

入出力例も参考にせよ．

注意点

すべての操作を終えた後，あなたのプログラムは直ちに終了しなければならない．終了しなかった場合のジャッジ結果は不定である．また，条件を満たさない不正な出力をした場合の結果も不定である (必ずしも WA になるとは限らない)．

すべての操作を終えてあなたのプログラムが終了した後，作られた画像が達成条件を満たしていれば正答とみなされる．

出力した後に，出力を flush しなければならないことに注意せよ．flush しなかった場合，TLE となることがある．

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にするとよい。

入出力例

W=5,\ H=5,\ T=10 のときの入出力例を示す．

実際のテストケースとして与えられる入力データは配布データに含まれるものと同一な 1 ケースのみであり，以下は入出力の具体例を示すための説明であることに注意せよ．

5 5 10

..##.
.####
####.
###..
.#...

2 4

1

3 3

1

3 0

0

-1 -1