Problem C
The Princess and the Pea

A single pea is hidden in one of the $M$ mattresses at court. Your job is to find it within $N$ nights. Luckily, the kind princess has agreed to help you. After a single night’s sleep on a pile of mattresses, she can determine with certainty whether she slept on the pea or not. Alas, she is a real princess, so she turns black and blue all over after spending a night on top of the pea. In that case, she needs an additional $S$ nights of sleep in the comfort of her own bed – which is guaranteed to be unsullied by pod fruits – before she is available again. You can use the daylight hours to move the piles of mattresses about as much as you want.

Interaction

You start by reading a single line with the integers $M$, $N$, and $S$, separated by spaces.

From there, interaction proceeds in rounds. Each round you can either perform a measurement or announce the answer.

1. To perform a measurement, your write a question mark followed by the list of mattresses you want checked. For instance, you can write “? 17 3 4 10” to ask the princess to spend the night on top of mattresses $3$, $4$, $10$, and $17$. (Observe that the ordering plays no role. After all, she is a real princess.) In general, you write “? $m_1$ $\cdots $ $m_ r$”, where $m_1$, $\ldots $, $m_ r$ are distinct integers separated by spaces, with $0<r\leq M$ and $0\leq m_ i < M$ for $1\leq i \leq r$. This corresponds to asking the princess to spend the night on top of those $r$ mattresses. On the next morning, she will report whether she slept on a pea (the input is “1” and she turns black and blue) or not (the input is “0” and she is fully rested). This costs a single night. If the princess is black and blue, she needs $S$ additional nights of rest before she is ready to help you again.

2. To announce the answer, you write an exclamation point followed by an integer, separated by space. For instance, you can write “! 3” to announce “the pea is in mattress $3$” to the court at breakfast. In general you write a line of the form “! $m$”, where $0\leq m< M$, to announce that the pea is in the $m$th mattress. This terminates the interaction. If indeed the pea is in the $m$th mattress, your program is acceptet, otherwise it will be rejected with the verdict wrong answer.

If the number of nights exceeds $N$, your program is rejected with the verdict wrong answer.

The mattresses are enumerated from $0$ to $M - 1$. There is exactly one pea. In the beginning, the princess is fully rested.

Points

There are six test groups. It always holds that $1\leq M \leq 1000$, $0\leq N\leq 1000$, and $0\leq S\leq 1000$. Moreover, $N$, $M$ and $S$ are chosen such that an optimal strategy finds the pea within at most $N$ nights.

Flushing the output buffer

The output of your program may get stuck in a buffer, which leads to the verdict time limit exceeded. To prevent this, you should ensure that the buffer is emptied each time you print. This is called flushing the output buffer.

In Python3:

print(x, flush=True)

In Java:

System.out.println(x);
System.out.flush();

In C++:

std::cout << x << "\n" << std::flush;

Explanation of samples

The interaction starts with you reading the integers $M=3$, $N=3$, and $S=1$. Thus, there are $3$ mattresses, and you have $3$ nights to find the pea. If the princess spends the night on top of the pea, she needs $1$ extra night of sleep before she can help you again. On the first day you arrange the mattresses so that the princess sleeps on top of two mattresses: $0$ and $1$.

In sample one, the pea is in mattress $0$. Accordingly, after the first night, the princess tells you “$1$”, meaning that she slept on the pea and has turned black and blue. Thus, she cannot help you before the third night. (She spends the second night in her own quarters to recuperate.) For the third night, you ask her to sleep on mattress $0$. Again, she answers “$1$” (having slept on top of the pea), turns black and blue, and wouldn’t be able to help you again before the fifth night.

You would not be able to wait that long, since you already used the $3$ nights at your disposal. Luckily, you can infer from the princess’s answer that the pea must be in mattress $0$.

In the second example, the pea is in mattress $2$. After the first night, which she spent on mattresses $0$ and $1$, the princess is fully rested and answers “$0$”. You can immediately infer that the pea must be in mattress $2$ and announce this proudly on the second day.

3 3 1

? 0 1

1

? 0

1

! 0

3 3 1

? 0 1

0

! 2