AT_tenka1_2013_final_c 天下一ジグソーパズルみたび

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_c 高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたパズル作家のショウヘイ君は、天下一プログラマーコンテストのポスターを下図のように$ N\ \times\ M $ のピースに分割したジグソーパズルを作った。 draw_puzzle("c0", 3, 3, [ "01", "00", "11", ],[ "101", "010", ]); 上下左右に隣り合うピースの一辺は一方が凸に他方が凹になっており、外周の辺は直線になっている。 ショウヘイ君は一度バラバラにしたポスターを、2つの辺がくっつくかどうかを試していき元々くっついていた辺を探すことで、元のポスターを復元するプログラムを制作することにした。 まず、入力が以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ P_{1,\ 1} $ $ P_{1,\ 2} $ $ P_{1,\ 3} $ $ P_{1,\ 4} $ $ P_{2,\ 1} $ $ P_{2,\ 2} $ $ P_{2,\ 3} $ $ P_{2,\ 4} $ $ ... $ $ P_{N\ \times\ M,\ 1} $ $ P_{N\ \times\ M,\ 2} $ $ P_{N\ \times\ M,\ 3} $ $ P_{N\ \times\ M,\ 4} $ - パズルの縦幅 $ N $、横幅 $ M $ ( $ 2\ \leq\ N,\ M\ \leq\ 8 $ ) 、質問回数の上限 $ Q $ ( $ 3\ \leq\ Q\ \leq\ 10000 $ ) が、スペースで区切られて、それぞれ整数で与えられる。 - 続く $ N\ \times\ M $ 行で、$ i $ 番目のピースの上辺 $ P_{i,\ 1} $、右辺 $ P_{i,\ 2} $、下辺 $ P_{i,\ 3} $、左辺 $ P_{i,\ 4} $が与えられる。ただし、$ P_{i,\ j}\ =\ 0 $は直線、$ P_{i,\ j}\ =\ 1 $は凸、$ P_{i,\ j}\ =\ 2 $は凹を意味する。 あなたのプログラムは、2つのピースのある辺と辺が繋がるかどうかを、以下の形式で標準出力を用いて質問することができる。 > ? $ a $ $ d_a $ $ b $ $ d_b $ - $ a $ 番目のピースの方向 $ d_a $ の辺と、$ b $ 番目のピースの方向 $ d_b $ の辺をつなげるのが正解かどうかを質問する。 - $ 1\ \leq\ a,\ b\ \leq\ N\ \times\ M $ - $ d_a $, $ d_b $は、上辺を$ 1 $、右辺を$ 2 $、下辺を$ 3 $、左辺を$ 4 $とする。 - 応答プログラムは、質問された辺がつながるのが正解であれば`yes`を、そうでなければ`no`を出力する。 最後に、ジグソーパズルの並べ方を以下の形式で標準出力を用いて回答する。 > ! $ p_{1,\ 1} $ $ d_{1,\ 1} $ $ p_{1,\ 2} $ $ d_{1,\ 2} $ $ ... $ $ p_{1,\ M} $ $ d_{1,\ M} $ $ p_{2,\ 1} $ $ d_{2,\ 1} $ $ p_{2,\ 2} $ $ d_{2,\ 2} $ $ ... $ $ p_{2,\ M} $ $ d_{2,\ M} $ $ ... $ $ p_{N,\ 1} $ $ d_{N,\ 1} $ $ p_{N,\ 2} $ $ d_{N,\ 2} $ $ ... $ $ p_{N,\ M} $ $ d_{N,\ M} $ - $ i $ 行目の $ j $ 列目に $ p_{i,\ j} $ 番目のピースを入力で与えられた上辺を方向 $ d_{i,\ j} $ にして置く。 - $ d_{i,\ j} $ は、上を$ 1 $、右を$ 2 $、下を$ 3 $、左を$ 4 $とする。 - ジグソーパズル全体の向きは問わない。すなわち、ジグソーパズル全体が正解に対して180度回転していても構わない。$ N\ =\ M $であれば90度または270度回転していても構わない。 - $ Q\ =\ 10000 $ の入力に正解すると、160 点満点に対して部分点として、50 点が与えられる。 - $ Q\ =\ 3000 $ の入力に正解すると、160 点満点に対して部分点として、上記とは別に 60 点が与えられる。 - 残り 50 点に対しては 25 の入力があり、入力を一つ正解するごとに部分点として 2 点が与えられる。各入力の $ N $, $ M $, $ Q $ を下表に示す。 $ N $$ M $$ Q $ 1571000 2751000 3851000 4581000 5661000 6661000 756500 865500 955500 1046500 1164500 1245200 1354200 1444100 154480 164470 174350 183440 193425 203325 213315 222310 23237 24225 25223 ``` ``` プログラムの出力プログラムへの入力2 2 100 0 0 1 2 0 1 2 0 0 0 2 2 1 1 0 0? 1 4 2 2no? 1 3 2 3yes! 1 4 2 2 4 1 3 2

N/A

N/A