実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
うさぎは H 行 W 列のマス目を何色かの色で塗り分けました。i (1≦i≦H) 行目 j (1≦j≦W) 列目のマスをマス (i,j) と呼ぶことにします。
うなぎはこのマス目に点対称な長方形がいくつ含まれているかが気になっています。
しかし、うさぎはマス目を見せてくれません。
うなぎは代わりに、以下のような質問をすることで点対称な長方形の個数を調べようとしています。
- 「マス (a,b) とマス (c,d) が同じ色かつ、マス (a,d) とマス (c,b) が同じ色」は正しいですか?
ただし、うさぎは気が短いので 4,500 回までしか質問に答えてくれません。
入出力
まず、マス目の行数・列数を表す 2 つの整数 H (1 ≦ H ≦ 5), W (1 ≦ W ≦ 100) が空白区切りで標準入力に与えられる。
H W
続いて、あなたのプログラムは 0 回以上 4,500 回以下の質問を行うことができる。
各質問ではまず、文字 ?
と 4 つの整数 a (1 ≦ a ≦ H), b (1 ≦ b ≦ W), c (a ≦ c ≦ H), d (b ≦ d ≦ W) を空白区切りで出力する。これは、「マス (a,b) とマス (c,d) が同じ色かつマス (a,d) とマス (c,b) が同じ色、は正しいですか?」という質問を表す。
? a b c d
すると、あなたのプログラムには yes
または no
の文字列が与えられる。
最後に、あなたのプログラムは、文字 !
と答えを空白区切りで出力しなければならない。
! answer
答えを出力した後、あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。
また、正しくない出力をした場合の結果も不定である(必ずしも WA
になるとは限らない)。
また、質問の回数制限を超えた場合も WA
になることに注意せよ。
あなたのプログラムが正しい答えを出力して終了した場合、正答とみなされる。
出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。
各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にしてもよい。
入出力例
うさぎが塗ったマス目が以下の画像のようなものであったときの入出力例を示す。
うさぎが塗ったマス目の例
説明 | プログラムの出力 | プログラムへの入力 |
---|---|---|
マス目の行数・列数が与えられている。 | 2 3 | |
「マス (1,1) とマス (2,3) が同じ色かつマス (1,3) とマス (2,1) が同じ色、は正しいですか?」という質問をしている。 | ? 1 1 2 3 | |
質問の答えが与えられている。 | yes | |
「マス (1,1) とマス (1,1) が同じ色かつマス (1,1) とマス (1,1) が同じ色、は正しいですか?」という質問をしている。 | ? 1 1 1 1 | |
質問の答えが与えられている。 | yes | |
「マス (1,1) とマス (1,3) が同じ色かつマス (1,3) とマス (1,1) が同じ色、は正しいですか?」という質問をしている。 | ? 1 1 1 3 | |
質問の答えが与えられている。 | no | |
マス目に含まれる点対称な長方形は 10 個であるという回答をしている。 | ! 10 |
マス目に含まれる点対称な長方形は以下の 10 個であるため、正解となる。
マス目に含まれる点対称な長方形