CF862D Mahmoud and Ehab and the binary string

Mahmoud 和 Ehab 现在进入了第四阶段。 Dr. Evil 拥有一个长度为 $n$ 的隐藏二进制字符串。他保证该字符串中至少有一个 $0$，且至少有一个 $1$。现在他想让 Mahmoud 和 Ehab 找到该字符串中某个 $0$ 的位置和某个 $1$ 的位置。为此，Mahmoud 和 Ehab 最多可以向 Dr. Evil 询问 $15$ 个问题。每次提问时，他们给出一个长度为 $n$ 的二进制字符串，Dr. Evil 告诉他们这个字符串与隐藏字符串的海明距离。海明距离定义为两个等长字符串中对应位置不同的字符的个数（关于海明距离的定义可见下面的注释部分）。 请帮助 Mahmoud 和 Ehab 找到这两个位置。 如果出现以下情况，你将得到 Wrong Answer 判定： - 你的提问不符合下面交互协议的要求； - 你总共询问次数严格超过 $15$ 次，且程序在超出询问次数后终止。请注意，你最多可以进行 $15$ 次提问和一次输出答案； - 你最终输出的答案不正确。 如果你未向标准输出输出任何内容，或忘记在所有输出后刷新输出流，也会得到 Idleness Limit Exceeded 判定（更多关于刷新输出流的信息请见下文）。如果你超过了最大可提问次数，应输出 0 并终止程序。在这种情况下，你会得到 Wrong Answer。若你未及时终止程序，可能会获得不确定的判定结果，因为流已被关闭。

输入的第一行为一个整数 $n$（$2 \leq n \leq 1000$），表示隐藏二进制字符串的长度。

要输出最终答案时，请输出 “! pos0 pos1”，其中 $pos0$ 和 $pos1$ 分别表示某个 $0$ 的位置和某个 $1$ 的位置（下标从 1 开始计数）。输出答案后别忘了刷新输出流！ 交互说明： - 你可以用 "? s" 的格式进行询问，其中 $s$ 是你的查询字符串。每次输出后记得刷新输出流！ - 每次提问后，你可以读取一个整数，表示隐藏字符串和查询字符串的海明距离。 各编程语言的刷新输出流方法： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请参考相关文档。 Hack 方式说明： 要 hack 他人，只需输出一个长度不超过 $1000$ 的二进制字符串，且该字符串中至少有一个 $0$ 和一个 $1$。

海明距离定义参考：[https://en.wikipedia.org/wiki/Hamming\_distance](https://en.wikipedia.org/wiki/Hamming_distance) 例如，若隐藏字符串为 $101$，第一次查询字符串为 $000$，海明距离为 $2$；第二次查询字符串为 $001$，海明距离为 $1$。 通过几次询问后，你发现第 $2$ 位是 $0$，第 $1$ 位是 $1$，因此你输出 "! 2 1"。 由 ChatGPT 5 翻译