P6982 [NEERC 2015] Jump

考虑一个称为 ONEMAX 的简单交互问题，其定义如下。 已知一个整数 $n$，存在一个长度为 $n$ 的隐藏二进制串 $S$。你唯一能做的就是向系统提交一个长度为 $n$ 的二进制串 $Q$，系统将返回数值 $\text{ONEMAX}(Q)$——即 $Q$ 与 $S$ 在对应位置上相同的位数。ONEMAX 问题的名称源于这样一个事实：该问题以及一个更简单的问题（当 $S = 11\ldots11$ 时，问题就变成了最大化 1 的个数，因此得名 ONEMAX）。 当 $n$ 为偶数时，存在一个类似但更难的问题，称为 JUMP。描述 JUMP 最简单的方式是利用 ONEMAX： $$ \text{JUMP}(Q)= \begin{cases} \text{ONEMAX}(Q) & \text{如果 } \text{ONEMAX}(Q)=n \text{ 或 } \text{ONEMAX}(Q)=n/2; \\ 0 & \text{否则。} \end{cases} $$ 基本上，通过 JUMP 你能看到的 ONEMAX 非零值只有 $n$（意味着你找到了隐藏串 $S$）和 $n/2$。 给定一个偶数 $n$ 作为问题规模，你需要通过交互式 JUMP 查询来解决隐藏串 $S$ 的问题。你的最终目标是做出一个查询 $Q$ 使得 $Q = S$。 ### 交互协议 首先，测试系统会告知比特串的长度 $n$。然后，你的程序发出查询，系统根据 JUMP 的定义给出回答。当程序发出的查询 $Q$ 满足 $Q = S$ 时，系统回答 $n$ 并终止，因此如果你的程序在读取到回答 $n$ 后还尝试读取或写入任何内容，将会失败。 查询次数的上限为 $n + 500$。如果你的程序发出了第 $n+501$ 次查询，你将得到“答案错误”的结果。如果你的程序过早终止，也会得到该结果。 如果你的查询包含错误字符（既不是 0 也不是 1），或者长度错误（不等于 $n$），系统将终止测试，你会得到“输出格式错误”的结果。 对于常见的违规情况，你将得到“超时”等结果。 最后，如果一切正常（例如你的程序在每个测试用例中都找到了隐藏串），你将得到“通过”的结果，此时你就成功解决了该问题。

输入流的第一行包含一个偶数 $n$（$2\le n\le 1000$）。接下来的输入行依次包含对应查询的答案。每个答案是一个整数——可能是 $0$、$n/2$ 或 $n$。每个答案独占一行。

要发出查询，请打印一行包含长度为 $n$ 的字符串，该字符串仅由字符 $0$ 和 $1$ 组成。打印查询后不要忘记输出换行符并刷新输出流。

翻译由 DeepSeek 完成