No.3347 Guess The Array
タグ : / 解いたユーザー数 29
作問者 :
noya2
Problem Statement
This is an interactive problem.
You are first given an integer $N$. The judge holds a hidden sequence $A$ of length $N$.
You may repeatedly ask the judge the following question.
- Create one sequence $B$ of any length and send $B$ to the judge. Here, $1\le |B| \le N$ must hold, and every element of $B$ must be an integer between $1$ and $N$, inclusive.
- The judge determines whether $B$ is a (not necessarily contiguous) subsequence of $A$ and tells you the result.
Identify the sequence $A$ using at most $5000$ questions.
Note that the sequence $A$ is fixed before the interaction begins and does not change depending on your questions.
Constraints
- $N$ is an integer
- $1 \leq N \leq 500$
- Each element of the sequence $A$ is an integer between $1$ and $N$, inclusive
Input and Output
This is an interactive problem (a problem in which your program and the judge system interact through input and output).
First, the length $N$ of the sequence is given.
$N$
After that, your program may ask questions in the following format, where $k=|B|$.
$?$ $k$ $B_1$ $B_2$ $\cdots$ $B_k$
After you send a question, the judge's response is given in the following format.
$S$
Here, $S$ is Yes or No, where
- $S$ being
Yesmeans that $B$ is a (not necessarily contiguous) subsequence of $A$. - $S$ being
Nomeans that $B$ is not a (not necessarily contiguous) subsequence of $A$.
When you output the answer, print it in the following format. After printing it, terminate your program.
$!$ $A_1$ $A_2$ $\cdots$ $A_N$
Notes
- Each time you output something, end it with a newline and flush standard output. Otherwise, the judge result may be TLE or WA.
- If a question is in an invalid format, or if you exceed the number of questions, the judge's response is undefined.
- Note that extra newlines are regarded as output in an invalid format.
- The output of your answer is not counted toward the number of questions.
Sample
| Program's output | Judge's output | Explanation |
|---|---|---|
5 | First, $N$ is given. The judge holds the hidden sequence $A=(1,2,3,4,5)$. | |
? 3 1 2 4 | The program sends $B = (1, 2, 4)$ to the judge as a question. | |
Yes | $B$ is contained in $A$ as a subsequence, so Yes is returned. | |
? 3 3 2 1 | The program sends $B = (3, 2, 1)$ to the judge as a question. | |
No | $B$ is not contained in $A$ as a subsequence, so No is returned. | |
! 1 2 3 4 5 | The program outputs $(1,2,3,4,5)$ as the answer. This matches $A$, so it is judged correct. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。