P13105 [GCJ 2019 Qualification] Dat Bae

一个研究联盟为他们的新数据中心建立了一个新的数据库系统。该数据库由一台主控计算机和 $N$ 台工作计算机组成，工作计算机的编号从 $0$ 到 $N-1$。每台工作计算机只存储一位信息……这看起来似乎很浪费，但这些数据非常重要！ 你被雇佣来评估数据库的以下指令： - TEST\_STORE ：主控计算机读取 ，这是一个长度为 $N$ 的二进制字符串，并将第 $i$ 位发送给第 $i$ 个工作计算机进行存储。随后，主控计算机会从工作计算机中读取这些位，并按照输入时的顺序返回给用户。 在正常情况下，TEST\_STORE 应该返回与输入相同的二进制字符串，但不幸的是，有 $B$ 台工作计算机损坏了！ 损坏的工作计算机能够正确存储分配给它们的位，但当主控计算机尝试从损坏的工作计算机读取数据时，将无法返回任何位。这导致 TEST\_STORE 操作只返回 $N-B$ 位，这些位是存储在未损坏工作计算机上的（按照它们的编号升序排列）。例如，假设 $N = 5$，第 0 和第 3 号工作计算机损坏（即 $B = 2$）。那么： - TEST\_STORE 01101 返回 111。 - TEST\_STORE 00110 返回 010。 - TEST\_STORE 01010 返回 100。 - TEST\_STORE 11010 也返回 100。 出于安全原因，数据库被隐藏在地下山体仓库中，因此每次调用 TEST\_STORE 都需要很长时间。你的任务是在最多 $F$ 次 TEST\_STORE 调用内，找出哪些工作计算机损坏了。 ### 交互协议 这是一个交互题。 程序开始时，应读取一行，包含一个整数 $T$，表示测试用例的数量。然后，你需要处理 $T$ 个测试用例。 对于每个测试用例，程序首先会读取一行，包含三个整数 $N$、$B$ 和 $F$，分别表示工作计算机的数量、损坏的工作计算机数量以及你可以发送的最多查询次数（如下所述）。 接下来，你可以向评测机最多发送 $F$ 行，每行包含一个长度为 $N$ 的字符串，每个字符为 0 或 1。每当你发送一行时，评测机会检查你是否已超过 $F$ 次调用。如果超过，评测机会返回一行，内容为 -1，然后结束所有通信并等待你的程序结束。否则，评测机会返回一个长度为 $N-B$ 的字符串，即 TEST\_STORE 操作的返回值，如上所述。 一旦你确定了 $B$ 个损坏的工作计算机的编号，可以通过发送一行 $B$ 个用空格分隔的整数（按升序排列）来提交答案。这一步不计入 $F$ 次调用之内。 如果你提交的 $B$ 个整数不是准确的损坏工作计算机编号，你将收到 Wrong Answer 判定，评测机会返回一行 -1，之后不再进行任何通信。如果你的答案正确，评测机会返回一行 1，随后进入下一个测试用例（或结束，如果这是最后一个测试用例）。

见交互协议。

见交互协议。

**交互样例** 以下交互过程符合测试集 1 的限制。 ``` t = readline_int() // 读取 t=2 n, b, f = readline_int_list() // 读取 n=5, b=2, f=10 printline 01101 to stdout // 以下四次输出与题目描述中的例子一致 flush stdout response = readline_str() // 读取 response=111（此时我们已可确定答案，后续查询仅为示例） printline 00110 to stdout flush stdout response = readline_str() // 读取 response=010 printline 01010 to stdout response = readline_str() // 读取 response=100 printline 11010 to stdout flush stdout response = readline_str() // 读取 response=100 printline 0 3 to stdout // 猜测答案。注意不要求用完所有 10 次查询。 flush stdout verdict = readline_int() // 读取 verdict=1，说明本测试用例正确！ n, b, f = readline_int_list() // 读取 n=2, b=1, f=10 printline 01 to stdout // 01 是一次查询，不是最终答案（如果想猜测只有 1 号损坏，应像下方一样输出） flush stdout response = readline_str() // 读取 response=1 printline 1 to stdout // 随意猜测 verdict = readline_str() // 读取 verdict=-1 exit // 退出以避免歧义性 TLE 错误 ``` 你可以使用本地测试工具在本地或平台上进行测试。要在本地测试，你需要让测试工具与你的代码并行运行；你可以使用我们的 [interactive runner](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请阅读该文件中的注释说明。 测试工具的使用说明已包含在工具的注释中。我们鼓励你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它**不是**真实的评测系统，可能会有不同的表现。 **数据范围** - $1 \leq T \leq 100$。 - $2 \leq N \leq 1024$。 - $1 \leq B \leq \min(15, N-1)$。 **测试集 1（14 分，公开）** - $F = 10$。 **测试集 2（20 分，隐藏）** - $F = 5$。 由 ChatGPT 4.1 翻译