問題一覧 > 通常問題

No.934 Explosive energy drink

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 184
作問者 : leafirbyleafirby / テスター : QCFiumQCFium
9 ProblemId : 3539 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-29 22:04:10

問題文

$20XX$年、ある$K$種類の魔剤を混ぜると爆発することが話題になりました。
しかし、具体的にどの$K$種類の魔剤を混ぜると爆発するのか,$K$の値といったことは知られていません。
そこで$Iot$くんに与えられた仕事は$K$種類の魔剤を特定することです。
ここに$N$種類$(K\le N)$の魔剤が無限本あります。
また、魔剤は種類ごとに、$1$から$N$まで番号が振られています。 特定の$K$種類の魔剤の内、一種類でも混ざってないと爆発しません。
爆発に必要な量は考えないものとして、$Iot$くんの代わりに特定してください。
ただし、あなたは以下の質問

  • 魔剤${a_1,a_2...a_M}$(ただし、$a_i=1,2,...N$のいずれか / $2\le M\le N$)を混ぜた時、爆発するか?
を$1333$回以下だけ質問することができます。

入出力

最初に標準入力から用意された魔剤の種類数$N(3\le N\le 1000)$が以下のように与えられる。
$N$
続いて、あなたのプログラムは標準出力に以下の形式の質問クエリを$1333$回まで行うことができる。
$?\ M$
$a_1\ a_2\ ...a_M$
この出力は,$M$本の魔剤${a_1,a_2,...a_M}$を混ぜると爆発するかという質問することを表す。$M$は整数で、$2\le M\le N$を満たさなければならない。
また、${a_1,a_2,...a_M}$は昇順ソートされてなければならず、空白区切りで出力しなければならない。
質問クエリを行うと、その回答が以下の形式で標準入力から与えられる。
$ans$
$M$本の魔剤を混ぜた時、爆発するならば$ans=1$であり、爆発しないのであれば$ans=0$である。
最後に、答えを以下の形式で出力しなければならない。
$!\ K$
$b_1\ b_2\ ...b_K$
まず、$K$は混ぜると爆発する魔剤の種類数を表す。そして、${b_1,b_2,...b_K}$は混ぜると爆発する魔剤の番号を表す。
ただし、昇順にソートしていなければならず、空白区切りで出力しなければならない。

注意

  • 出力のあと、標準出力をflushしなければならない。
  • 質問クエリの後、その結果を必ず受け取ること。
  • 答えを出力したあとはプログラムをすぐに終了しなければならない。
  • $1333$回以下のクエリで必ず答えを求められることが保証される。
  • $N$種類の魔剤の中には必ず$K$種類の爆発する魔剤が含まれていることが保証される。
  • $2\le K$であることが保証される。

サンプル

サンプル1
入力
3
0
1
0
1
出力
? 2
1 2
? 2
2 3
? 2
1 3
? 3
1 2 3
! 2
2 3

  • 魔剤1と魔剤2を混ぜると爆発しないので$ans=0$です。
  • 魔剤2と魔剤3を混ぜると爆発するので$ans=1$です。
  • 魔剤1と魔剤3を混ぜると爆発しないので$ans=0$です。
  • 魔剤1と魔剤2と魔剤3を混ぜると爆発するので$ans=1$です。
よって爆発する魔剤の種類数は$2$、番号は$2$と$3$と分かります。
同じケースの不正解の入出力例を挙げます。
入力
3
0
1
0
出力
? 2
1 2
? 2
2 3
? 2
1 3
? 3
1 3 2
$4$回目のクエリで、$a_i$が昇順になってないのでWAと判定されます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。