#P18948. [Mladen Manev 2021 A4] binstring / 猜二进制串

[Mladen Manev 2021 A4] binstring / 猜二进制串

猜二进制串

这是交互题。交互器固定一个长度为偶数 NN 的二进制秘密串 hh。每次可以询问一个同长二进制串 ss,得到:

  • 2:所有位置都相同;
  • 1:恰好 N/2N/2 个位置相同;
  • 0:其他情况。

最多询问 1501 次,最后输出秘密串。

交互协议

首先读入 NN,其中 2≤N≤10002\le N\le1000,NN 为偶数。

询问时输出 ? s 并刷新输出,随后读入一个整数回答。ss 必须恰好有 NN 个字符,且每个字符是 0 或 1。

确定答案后输出 ! h,刷新输出并退出。最终回答不计作询问;询问超过 1501 次或格式不合法会判错。

交互示意

当秘密串为 0101 时,询问 ? 0000 得到 1,询问 ? 0101 得到 2,随后可以输出 ! 0101。

题包说明

原题为 play(n)、compare_string(s)、submit_string(s) 的函数交互。本题包使用等价的标准输入输出交互协议。数据文件内的秘密串由交互器读取,选手只能读到长度和回答。

来源与数据说明

2021 年 Dr. Mladen Manev,A4,原题名 binstring。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。