← 返回题目列表

Codeforces · 862/D

D. Mahmoud 和 Ehab 以及二进制字符串

中文机器翻译题面 查看原题

Mahmoud 和 Ehab 现在处于第四阶段。

邪恶博士有一个隐藏的长度为 n 的二进制字符串。他保证里面至少有一个‘0’符号和至少一个‘1’符号。现在他希望 Mahmoud 和 Ehab 找到任何“0”符号和任何“1”符号的位置。为此,Mahmoud 和 Ehab 可以向邪恶博士询问最多 15 个问题。他们告诉邪恶博士一些长度为 n 的二进制字符串,邪恶博士告诉这两个字符串之间的汉明距离。两个相同长度的二进制串之间的汉明距离是它们具有不同符号的位置的数量。您可以在下面的注释部分找到汉明距离的定义。

帮助 Mahmoud 和 Ehab 找到这两个位置。

如果出现以下情况,您将得到错误答案判决:

- 您的查询不满足下述交互协议。
- 您提出的问题严格超过 15 个,并且您的程序在超出查询限制后终止。请注意,您最多可以进行 15 个询问和 1 个回答查询。
- 您的最终答案不正确。

如果超过最大查询数,您应该以 0 终止,在这种情况下您将得到错误答案,如果您不终止,您可能会收到任何判决,因为您将从关闭的流中读取。

输入

输入的第一行将包含一个整数 n (2 ≤ n ≤ 1000) - 隐藏二进制字符串的长度。

互动

要提出问题,请使用格式“? s”(不带引号),其中 s 是查询字符串。不要忘记在打印查询后刷新输出!

每次查询后,您可以从标准输入读取一个整数 - 隐藏字符串和查询字符串之间的汉明距离。

要刷新输出,您可以使用:-

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

黑客攻击。

要破解某人,只需打印一个长度最多为 1000 的二进制字符串,其中至少包含一个“0”和至少一个“1”。

输出

要打印最终答案,请打印“! pos0 pos1”(不带引号),其中 pos0 和 pos1 是字符串中某些“0”和某些“1”的位置(字符串以 1 为索引)。打印答案后不要忘记刷新输出!

示例

输入 #1

3
2
1
3
2
1
0

输出 #1

? 000
? 001
? 010
? 011
? 100
? 101
! 2 1

注意

汉明距离定义:https://en.wikipedia.org/wiki/Hamming_distance

在第一个测试用例中,隐藏的二进制字符串是101,第一个查询是000,所以汉明距离是2。在第二个查询中,隐藏的字符串仍然是101,查询是001,所以汉明距离是1。

经过一些查询,您发现位置 2 的符号是“0”,位置 1 的符号是“1”,因此打印“! 2 1”。