P6982 [NEERC 2015] Jump

Consider a toy interactive problem ONEMAX, which is defined as follows. You know an integer $n$, and there is a hidden bit string $S$ of length $n$. The only thing you may do is to present the system with a bit string $Q$ of length $n$, and the system will return the number $\text{ONEMAX}(Q)$, which is the number of bits that coincide in $Q$ and $S$ at the corresponding positions. The name of the ONEMAX problem comes from the fact that this problem is similar to a simpler one where $S = 11\ldots11$, so the problem turns into maximizing (MAX) the number of ones (ONE). When $n$ is even, there is a similar (but harder) interactive problem called JUMP. The simplest way to describe JUMP is by using ONEMAX: $$ \text{JUMP}(Q)= \begin{cases} \text{ONEMAX}(Q) & \text{if } \text{ONEMAX}(Q)=n \text{ or } \text{ONEMAX}(Q)=n/2; \\ 0 & \text{otherwise.} \end{cases} $$ Basically, the only nonzero values of ONEMAX that you can see with JUMP are $n$ (which means you have found the hidden string $S$) and $n/2$. Given an even integer $n$, the problem size, you have to solve the JUMP problem for the hidden string $S$ by making interactive JUMP queries. Your task is to eventually make a query $Q$ such that $Q = S$. ### Interaction Protocol First, the judging system tells you the length of the bit string $n$. Then, your solution sends queries, and the system answers them as defined by JUMP. When your solution sends a query $Q$ such that $Q = S$, the system answers $n$ and terminates. Therefore, if your solution tries to read or write anything after reading the answer $n$, it will fail. The limit on the number of queries is $n + 500$. If your solution sends the $(n + 501)$-th query, you will get a “Wrong Answer”. You will also get this outcome if your solution terminates too early. If your query contains invalid characters (neither 0 nor 1), or has an incorrect length (not equal to $n$), the system will stop the test and you will get a “Presentation Error”. You may get “Time Limit Exceeded” and other errors for the usual violations. Finally, if everything is OK (for example, your solution finds the hidden string) on every test, you will get “Accepted”. In that case, you have solved the problem.

The first line of the input stream contains an even integer $n$ ($2 \leq n \leq 1000$). The following lines of the input stream contain the answers to the corresponding queries. Each answer is an integer, either $0$, $n/2$, or $n$. Each answer is on its own line.

To make a query, print one line containing a string of length $n$ consisting only of the characters 0 and 1. Do not forget to print a newline and flush the output stream after printing your query.

Translated by ChatGPT 5