Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
これはインタラクティブな問題です。
問題文
ゐろはちゃんはいろはちゃんの偽者です。いろはちゃんは常に本当のことを言い、ゐろはちゃんはほぼ常に嘘をつきます。
また、二人はある立方体を共有しています。その立方体の各頂点には 0 から 7 までの整数が 1 つずつ割り当てられており、異なる頂点には異なる数が割り当てられています。
あなたはこの二人を見分けるために、二人に何回か質問をすることにしました。
あなたは以下の質問を、二人に同時にすることができます。
質問: 0 以上 7 以下の相異なる 3 個の整数の組 (X, Y, Z) に対し、それらの数が割り当てられている 3 つの頂点を通る平面で立方体を切ったときの切り口の形を聞く。
二人の回答は、Square
、Rectangle
、Triangle
のいずれかです。いろはちゃんは、指定された平面が立方体の 1 つの面と一致する、つまり切り口の形が正方形といえるときはSquare
、切り口の形が正方形でない長方形のときはRectangle
、正三角形のときはTriangle
と回答します。ゐろはちゃんは、最初の質問に対してだけは必ずいろはちゃんと同じ回答を言いますが、 2 回目以降の質問に対しては、必ずいろはちゃんの回答とは異なる回答を言います。例えば、いろはちゃんが、 2 回目以降のある質問に対してRectangle
と回答するとき、ゐろはちゃんはSquare
とTriangle
のうちのどちらか一方を回答します。
あなたは二人に最大 11 回質問することができます。ただし、同じ整数の組み合わせを複数回質問することはできません。例えば、整数の組 (1, 3, 6) について質問をした後、 (1, 3, 6) や (3, 1, 6) 、 (6, 1, 3) などについて質問をすることはできません。
回答者 1 と回答者 2 のどちらがいろはちゃんか判定してください。
入出力
この問題はインタラクティブ形式です。大事なことなので 2 度言いました。
この問題においては、最初に入力は与えられない。最初からクエリを送ることを繰り返す。
質問のクエリは次の形式で標準出力へ出力せよ。 行末には改行を出力せよ。
?\ X\ Y\ Z
( X, Y, Z は 0 以上 7 以下の相異なる整数)
これに対するクエリの答えは、次の形式で標準入力から与えられる。
S\ \ T
S は回答者 1 の回答、 T は回答者 2 の回答で、どちらもSquare
、Rectangle
、Triangle
のいずれかである。
解は次の形式で標準出力へ出力せよ。行末には改行を出力せよ。
!\ \ t
回答者 1 がいろはちゃんであるならば t=1、回答者 2 がいろはちゃんであるならば t=2 とせよ。
実装上の注意
- 出力のあと、標準出力を flush しなければならない。 そうでないときは
TLE
の可能性がある。 - 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
- 質問回数が 11 回を超えた場合、および同じ数の組み合わせについての質問を複数回行った場合、
WA
となる。 - クエリの形式が正しくない場合の挙動は定義されていない。