M - Pakenのうさぎ 解説 /

実行時間制限: 1 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

これはインタラクティブな問題です。

今年のPakenでは、いつでももふもふできるうさぎを置くことになりました。
しかし、手頃なうさぎが見つからないので、一時的に部員であるanmichiをうさぎにしようと決まりました。

今ここに、人間をうさぎに変えるためのドロップが N 種類あり、1 から N までの番号が振られています。
このうち効果があるのは 2 種類だけであり、これらを 2 つ両方食べた場合にのみ人間はうさぎになりますが、効果がある 2 種類がどれかは分かりません。他のドロップは人間に何ら影響を及ぼしません。
ドロップはとても苦いので、anmichiが食べるのは効果のある 2 つだけにしたいです。

anmichiが食べるべきドロップを識別するため、25 人の他の部員たちがそれぞれドロップを食べ、うさぎになったかどうか実験することで目的のドロップを識別することにしました。
1 回の実験では、ある部員が N 個のドロップのうち 0 個以上のいくつかのドロップを選び、一気に食べることによって、うさぎになったかどうかを判定します。
ただし、1 人の部員を 2 回以上の実験に使う事はできないので、高々 25 回しか実験を行えません。

適切に他の部員が食べるドロップを決めることで、効果のあるドロップを特定してください。
なお、それぞれのドロップは他の部員が全員食べられるくらい十分な量あるものとします。

制約

  • 2 \leq N \leq 6000

入出力

最初に、N が次の形式で標準入力から与えられます。

N

次に、クエリを繰り返し送ります。この回数は 25 回以内でなければなりません。
部員に飲ませるドロップの数を K 個として、K と部員に飲ませるドロップの番号を K 個空白区切りで昇順に出力し、最後に改行してください。 

? K A1 A2 \ldots AK

これに対するクエリの答えは、次の形式で与えられます。

s

s は Rabbit,Humanのいずれかです。Rabbit の場合部員がうさぎになった事、Human の場合部員がうさぎにならなかった事を意味します。


答えを出力する際は、効果のあるドロップの番号をそれぞれ x,y (x < y)として、次のように出力してください。

! x y

なお、答えの出力は部員へのクエリ回数に含まれないことに注意してください。

注意

  • 出力の最後に改行を含めて出力しなければなりません。その後、標準出力を flush しなければなりません。 そうでない場合は TLE の可能性があります。
  • 答えを出力した後、プログラムをすぐに終了しなければならなりません。そうでないときの挙動は定義されていません。
  • 出力の答えが間違っている場合の挙動は定義されていません (WAとは限りません)。

入出力例

この入出力例では、N = 4 であり、ドロップ 1 と 3 に効果がある場合のジャッジ側とのやり取りの一例を示しております。
なお、これはあくまでも入出力例であり、意味のあるやりとりをしているとは限らない事に注意してください。

自分のプログラムへの入力（ジャッジ側の出力） 自分のプログラムの出力
4
? 2 1 3
Rabbit
? 3 1 2 4
Human
? 0
Human
? 4 1 2 3 4
Rabbit
! 1 3
ここで、最後に ! 3 1 と出力した場合に正解にならない事に注意してください。x < y を満たす必要があります。

writer: kaage

Score : 600 points

Problem Statement

This is an interactive task.

Today, a rabbit to pat is needed by members of Paken.
However, they haven't found apt rabbits. Then, it has been decided to equip anmichi who is one of the members as a rabbit.

Now, there are N kinds of pills to transform a human into a rabbit.
Only two pills of them are effective and only if anmichi takes both of two pills, anmichi becomes a rabbit. We don't know which are the effective pills. Other pills don't influence on him.
The pills don't taste good, so anmichi want to take only effective pills.

To recognize the effective pills, other 25 members taking them and confirm whether they are rabbits or humans.

Each members have to take the pills at once because they must achieve this mission urgently.

Your tasks is to recognize the effective pills by deciding the pills for other members to take.
You can assume that there is enough pills for other each members to take.

Constraints

  • 2 \leq N \leq 6000

Input and Output

First, N is given from Standard Input in the following format.

N

Next, you send queries repeatedly. This frequency have not to be more than 25. Let the number of pills for a member to take be K and print K and number of pills to take in ascending order to Standard Output. In addition, print linefeed code in the end of line.

? K A1 A2 … AK

The answers to this queries is given from Standard Input in the following format.

s

s is Rabbit or Human。These mean whether the member becomes a rabbit.

Finally, you answer to this problem. Let the numbers of effective pills be x and y ( x < y ) and print x and y to Standard Output in the following format.

! x y

Besides, printing the answer is not included in the number of queries.

Judgement

  • You have to flush Standard Output after each output. Otherwise, you can get TLE .
  • After you print the answer, the program has to be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined.

writer: kaage