問題一覧 > 通常問題

No.934 Explosive energy drink

レベル : / AI推定難易度 : 525 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 194
作問者 : leafirby / テスター : QCFium
お気に入りにしたユーザー ProblemId : 3539 / 自分の提出
問題文最終更新日: 2019-11-29 22:04:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 232 (順位表) の他の問題:

Problem Statement

In the year $20XX$, it became a hot topic that mixing certain $K$ types of energy drinks causes an explosion.
However, neither which specific $K$ types of energy drinks explode when mixed, nor the value of $K$, is known.
So the job given to $Iot$ is to identify the $K$ types of energy drinks.
Here there are $N$ types $(K\le N)$ of energy drinks, with an infinite number of bottles of each.
The energy drink types are numbered from $1$ to $N$. If even one of the specific $K$ types of energy drinks is not mixed in, there is no explosion.
Disregarding the amount required for an explosion, identify them on behalf of $Iot$.
However, you may ask the following question

  • When energy drinks ${a_1,a_2...a_M}$ (where $a_i=1,2,...N$, any one of these values / $2\le M\le N$) are mixed, do they explode?
at most $1333$ times.

Input and Output

First, the number of types of energy drinks prepared, $N(3\le N\le 1000)$, is given from standard input as follows.
$N$
Then, your program may make up to $1333$ question queries to standard output in the following format.
$?\ M$
$a_1\ a_2\ ...a_M$
This output represents asking whether mixing the $M$ energy drinks ${a_1,a_2,...a_M}$ causes an explosion. $M$ must be an integer satisfying $2\le M\le N$.
Also, ${a_1,a_2,...a_M}$ must be sorted in ascending order and printed separated by spaces.
After you make a question query, its answer is given from standard input in the following format.
$ans$
If mixing the $M$ energy drinks causes an explosion, $ans=1$; if it does not, $ans=0$.
Finally, you must output the answer in the following format.
$!\ K$
$b_1\ b_2\ ...b_K$
First, $K$ represents the number of types of energy drinks that explode when mixed. Then, ${b_1,b_2,...b_K}$ represent the numbers of the energy drinks that explode when mixed.
They must be sorted in ascending order and printed separated by spaces.

Notes

  • After each output, you must flush standard output.
  • After a question query, be sure to receive its result.
  • After outputting the answer, your program must terminate immediately.
  • It is guaranteed that the answer can always be determined with at most $1333$ queries.
  • It is guaranteed that the $N$ types of energy drinks always include the $K$ types of explosive energy drinks.
  • It is guaranteed that $2\le K$.

Sample

Sample 1
Input
3
0
1
0
1
Output
? 2
1 2
? 2
2 3
? 2
1 3
? 3
1 2 3
! 2
2 3

  • Mixing energy drink 1 and energy drink 2 does not cause an explosion, so $ans=0$.
  • Mixing energy drink 2 and energy drink 3 causes an explosion, so $ans=1$.
  • Mixing energy drink 1 and energy drink 3 does not cause an explosion, so $ans=0$.
  • Mixing energy drink 1, energy drink 2, and energy drink 3 causes an explosion, so $ans=1$.
Therefore, we can tell that the number of types of explosive energy drinks is $2$, and their numbers are $2$ and $3$.
Here is an example of incorrect input and output for the same case.
Input
3
0
1
0
Output
? 2
1 2
? 2
2 3
? 2
1 3
? 3
1 3 2
In the $4$th query, $a_i$ is not in ascending order, so it is judged as WA.

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