問題一覧 > 通常問題

No.934 Explosive energy drink

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

問題文

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

  • 魔剤a1,a2...aM(ただし、ai=1,2,...Nのいずれか / 2MN)を混ぜた時、爆発するか?
1333回以下だけ質問することができます。

入出力

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

注意

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

サンプル

サンプル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、番号は23と分かります。
同じケースの不正解の入出力例を挙げます。
入力
3
0
1
0
出力
? 2
1 2
? 2
2 3
? 2
1 3
? 3
1 3 2
4回目のクエリで、aiが昇順になってないのでWAと判定されます。

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