A - Appraiser Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

この問題は インタラクティブ な問題であり、 ジャッジは適応的(adaptive) です。詳しくは注意点を参照してください。
また、問題文中のパラメータは N=1000,M=10,Q=950 で固定されています。

硬貨が N 枚あり、 1,2,\dots,N の番号が付けられています。
これらの硬貨のうち、丁度 M 枚が偽物です。

鑑定士は 1 度の鑑定で 2 つの硬貨が同種か異種かを判定できます。厳密には、

  • 2 つの硬貨が「双方とも本物」「双方とも偽物」のどちらかであれば、同種と判定する。
  • そうでないとき、異種と判定する。

Q 回以下の鑑定で、全ての偽物の硬貨を特定してください。

制約

  • \color{red}{N = 1000}
  • \color{red}{M = 10}
  • \color{red}{Q = 950}

入出力

この問題はインタラクティブな問題です。
最初に、 N,M,Q を標準入力から受け取ってください。 

N M Q


次に、以下の流れで鑑定を 0 回以上 Q 回以下行ってください。

まず、次の形式で標準出力に出力することで、硬貨 x,y を鑑定することを表します。 (末尾に改行を入れること。)

? x y

ここで、 x,y は 1 以上 N 以下の相異なる整数である必要があります。

これに対するジャッジシステムの応答は、以下の 3 通りです。

0

応答が 0 であるとき、硬貨 x,y が同種であることを表します。

1

応答が 1 であるとき、硬貨 x,y が異種であることを表します。

-1

応答が -1 であるとき、不当な鑑定であることを表します。具体的には

  • 出力した x,y が制約を満たさなかった
  • Q 回を超えて鑑定が行われた

の少なくともひとつが満たされた際にこの応答を行います。
この応答を受け取った場合、プログラムはすでに不正解とみなされています。直ちにプログラムを終了してください。


最後に、次の形式で標準出力に出力することで、硬貨 A_1,A_2,\dots,A_{M} が偽物であると解答します。 (末尾に改行を入れること。)

! A_1 A_2 \dots A_{M}

ここで、 A_i は 1 以上 N 以下の相異なる整数である必要があります。
この出力の後、直ちにプログラムを終了してください。

なお、全ての出力について、出力が指定された形式を満たさなかった場合もプログラムが不正解とみなされます。 その後 -1 が返答されるので、その場合も直ちにプログラムを終了してください。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。 そうしなかった場合、ジャッジ結果が TLE や WA となる可能性があります。
  • 解答を出力したら (または -1 を受け取ったら) ただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
  • 余計な改行は不正なフォーマットの出力とみなされることに注意してください。
  • この問題のジャッジシステムは、適応的(adaptive)です。 つまり、ジャッジシステムは、任意のタイミングにおいて、整合性がとれる限り、偽物の硬貨として想定しているものを変更する可能性があります。詳しくは入出力例も参照してください。

入出力例

この入力では N=5,M=2,Q=10 であり、ジャッジシステムは最初硬貨 1,2 が偽物であると想定しています。

なお、この例は制約を満たさないので、ジャッジには含まれないことに注意してください。

入力 出力 説明
5 2 10 N,M,Q が与えられます。
? 1 2 硬貨 1,2 について鑑定を行います。
0 硬貨 1,2 は同種だと判定します。
? 1 3 硬貨 1,3 について鑑定を行います。
1 硬貨 1,3 は異種だと判定します。
? 1 4 硬貨 1,4 について鑑定を行います。
1 硬貨 1,4 は異種だと判定します。
! 1 2 硬貨 1,2 が偽物だと解答します。
確かに硬貨 1,2 は偽物だと想定されていますが、硬貨 3,4 を偽物であると想定しても整合性が取れます。
よって、ジャッジシステムは偽物の硬貨として想定しているものを硬貨 3,4 に変更できます。
これにより、ジャッジシステムは不正解の判定を下すこともあります。

Score : 600 points

Problem Statement

This problem is interactive, and the judge is adaptive. See the notes for details.
Also, the parameters in the problem statement are fixed at N=1000, M=10, Q=950.

There are N coins numbered 1, 2, \dots, N.
Exactly M of these coins are counterfeit.

An appraiser can, in one appraisal, determine whether two coins are of the same type or different types. Specifically:

  • If the two coins are both genuine or both counterfeit, they are judged to be of the same type.
  • Otherwise, they are judged to be of different types.

Identify all the counterfeit coins using at most Q appraisals.

Constraints

  • \color{red}{N = 1000}
  • \color{red}{M = 10}
  • \color{red}{Q = 950}

Interaction

This is an interactive problem.
Initially, receive N, M, and Q from Standard Input:

N M Q


Next, you can perform appraisals between 0 and Q times, inclusive, as follows.

First, by outputting to Standard Output in the following format, you indicate that you are appraising coins x and y. (Include a newline at the end.)

? x y

Here, x and y must be distinct integers between 1 and N, inclusive.

In response, the judge system will reply with one of the following three responses.

0

If the response is 0, it means that coins x and y are of the same type.

1

If the response is 1, it means that coins x and y are of different types.

-1

If the response is -1, it means that the appraisal is invalid. Specifically, this response is given when at least one of the following conditions is met:

  • The outputted x and y does not satisfy the constraints.
  • The number of appraisals exceeds Q.

If you receive this response, your program is considered incorrect. Terminate your program immediately.


Finally, by outputting to Standard Output in the following format, you answer that coins A_1, A_2, \dots, A_{M} are counterfeit. (Include a newline at the end.)

! A_1 A_2 \dots A_{M}

Here, A_i must be distinct integers between 1 and N, inclusive.
After this output, terminate your program immediately.

If any of your outputs do not meet the specified format, your program will be considered incorrect. The judge will then respond with -1, so in that case, terminate your program immediately.

Notes

  • Every time you output, include a newline at the end and flush Standard Output. Failure to do so may result in a verdict of TLE or WA.
  • After outputting your answer (or receiving -1), terminate your program immediately. Otherwise, the verdict is indeterminate.
  • Beware that unnecessary newlines are considered as malformed.
  • The judge for this problem is adaptive. That is, at any point, as long as consistency can be maintained, the judge may change which coins are counterfeit. See the sample interaction for details.

Sample Interaction

In this interaction, N=5, M=2, Q=10, and the judge initially considers coins 1 and 2 to be counterfeit.

Note that this example does not meet the constraints and is not included in the judge.

Input　 Output Explanation
5 2 10 N, M, and Q are given.
? 1 2 You appraise coins 1 and 2.
0 Coins 1 and 2 are judged to be of the same type.
? 1 3 You appraise coins 1 and 3.
1 Coins 1 and 3 are judged to be of different types.
? 1 4 You appraise coins 1 and 4.
1 Coins 1 and 4 are judged to be of different types.
! 1 2 You answer that coins 1 and 2 are counterfeit.
Indeed, coins 1 and 2 are considered counterfeit, but it is also possible to consider coins 3 and 4 as counterfeit while maintaining consistency.
Therefore, the judge may change the counterfeit coins to 3 and 4.
As a result, the judge may judge this answer as incorrect.