G - Good Game

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : 100

くろうさ「交互に石を置いていく」

しろうさ「ゲームかな?」

くろうさ「自分の色の石が 2 \times 2 のブロックになっちゃダメ」

しろうさ「完全に理解した」

くろうさ「手番は選ばせてあげるよ」

問題文

くろうさとしろうさは以下のようなゲームをしようとしている.

  • HW 列のマス目に,くろうさは黒石を,しろうさは白石を置いていく.
  • 最初しろうさは先手か後手かを選び,その後交互に 1 つずつ石を置いていく.
  • 既に石が置いてあるマスに石を置くことはできない.
  • 自分の色の石が 2 \times 2 のブロックになってはならない.すなわち,ある格子点を共有する 4 つのマス全てに自分の石が置かれているという状態になってはならない.
  • 先に石を置けなくなった方の負け.

しろうさの代わりにこのゲームをプレーし勝利するプログラムを作成せよ.

なお,ゲームは T 回連続で行われるので,その全てに勝利しなければならない.

制約

  • 1 \leq T \leq 25
  • 1 \leq H,W \leq 40

部分点

  • H, W が共に偶数である全てのテストケースに正解した場合は,25 点が与えられる.
  • 全てのテストケースに正解した場合は,上記とは別に 75 点が与えられる.

入出力

  1. 整数 T が標準入力に与えられる.
  2. 以下が T 回繰り返される.
    1. 整数 H, W が空白区切りで標準入力に与えられる.
    2. あなたのプログラムは First または Second と出力しなければならない.それぞれ先手・後手を選択することを表す.
    3. 勝敗が決まるまで以下を繰り返す.
      • 自分の手番の場合:2 つの整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) を空白区切りで出力する.これは r 行目 c 列目のマスに白石を置くことを表す.
      • 相手の手番の場合:2 つの整数 r, c (0 \leq r \leq H-1, 0 \leq c \leq W-1) が空白区切りで標準入力に与えられる.これは r 行目 c 列目のマスに黒石が置かれたことを表す.ただし,黒石を置くことのできるマスが存在しなかった場合は代わりに -1 -1 が標準入力に与えられる.この場合はしろうさの勝利となり,ゲームは終了する.

入出力例も参考にせよ.

注意点

T 回目のゲームが終了した後,あなたのプログラムは直ちに終了しなければならない. 終了しなかった場合のジャッジ結果は不定である. また,正しくない出力をした場合の結果も不定である(必ずしも WA になるとは限らない).

あなたのプログラムが全てのゲームに勝利したのちに終了した場合,正答とみなされる.

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

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

入出力例

入力 出力 説明
2 T が与えられている.
2 1 H, W が与えられている.
Second 後手を選んでいる.
1 0 くろうさが 1,0 に黒石を置いている.
0 0 しろうさが 0,0 に白石を置いている.
-1 -1 黒石を置くことができるマスが存在しないことを表している.
1 1 H, W が与えられている.
First 先手を選んでいる.
0 0 しろうさが 0,0 に白石を置いている.
-1 -1 黒石を置くことができるマスが存在しないことを表している.