#SYUCT13J. 深空回声
深空回声
题目描述
深空探测器“远眺一号”的内存中保存着一个长度为 的二进制串
巡检确认, 中恰好有 个字符 1,即
地面站的任务是还原出原始串 。
地面站的深空天线只能发送长度恰好为 的二进制对照串
探测器会返回 与 的汉明距离
$$d(S,T)=\left|\left\{i\mid 1\le i\le n,\ s_i\ne t_i\right\}\right|.$$返回的是完整的距离数值,而不是距离的奇偶性。
你的程序需要在最多 次询问内还原出原始串 。
交互流程
- 交互器首先向你的程序输出一行两个整数 和 (,),用空格分隔。
- 每次询问,你的程序向交互器输出一行
? T,其中 是一个长度为 的 0/1 串;交互器回复一行一个整数 (),表示 与 的汉明距离。 - 询问次数不能超过 次。若你发起第 次询问,交互器会回复一行
-1并终止交互;此时你的程序必须立即正常退出,任何后续读写都可能导致判题失败。 - 当你确定 后,输出一行
! S,其中 是你还原的长度为 的 0/1 串,然后正常退出,无需等待任何回复。
注意事项
- 每次输出后必须立即刷新输出缓冲区。C++ 使用
std::endl或fflush(stdout)均可。 - 交互器是非自适应的: 在交互开始前就已经确定,不会随你的询问而改变。
- 若你的任何一行输出不符合上述格式(前缀标记、长度、字符集),交互器会立即判定你的输出错误并终止交互。
- 本题仅支持 C++(GNU g++20)提交。
输入格式
第一行,交互器向你输出两个整数 ()和 (),用空格分隔。
随后,每当且仅当你发出一次格式合法的询问时,交互器会输出一行一个整数 ()。若你超出询问次数上限,交互器输出 -1 后终止交互。
输出格式
- 每次询问输出一行
? T; - 确定答案后输出一行
! S; - 询问次数不得超过 次;
- 每次输出后必须立即刷新输出缓冲区。
提示
下面是一次合法交互示例,其中 、、 0110:
(交互器输出)4 2
(你的输出) ? 0000
(交互器输出)2
(你的输出) ? 1111
(交互器输出)2
(你的输出) ? 1000
(交互器输出)3
(你的输出) ! 0110
这段记录只用于展示一次格式合法且最终答案正确的交互过程;前三次询问本身并不能唯一确定隐藏串,不应视为完整求解算法。
设 表示 的前 位中字符 1 的数量。若发送的对照串 满足前 位为 1、其余位为 0,则返回的距离满足
因此可以由 计算 。更一般地,若把任意位置集合 中的位设为 1,其余位设为 0,也可以由返回的汉明距离计算 中字符 1 的数量。