P8135 [ICPC 2020 WF] QC QC

ICPC2020 WF H

创新可计算质量控制（ICQC）开发了一种突破性的机器，用于执行质量控制。得益于其新颖的深度智能技术，ICQC 质量控制（QC）机器可以以 $100\%$ 的准确率自动检测任何现有机器的制造错误，无论是咖啡机、星际飞船还是量子计算机。 ICQC 现在正在建立其工厂以生产这些 QC 机器。与任何其他制造过程一样，生产的机器中会有一部分出现故障，这些需要被发现并丢弃。幸运的是，ICQC 恰好有产品可以检测故障机器！ 显然，ICQC 不应该简单地让 QC 机器自检，因为故障机器可能会错误地将自己分类为正常工作。相反，ICQC 将在夜间让每天生产的 $n$ 台机器相互测试。特别是，在夜间的每个小时，每台 QC 机器可以检查另一台 QC 机器，同时被另一台 QC 机器检查。 如果执行检查的机器是正常的，它将正确报告被测试机器是正常还是故障，但如果执行检查的机器是故障的，它可能报告任一结果。如果机器 A 多次用于测试机器 B，它每次都会返回相同的结果，即使机器 A 是故障的。具体的测试计划不需要提前固定，因此第二小时夜间的机器检查安排可以基于第一小时测试的结果进行。 ICQC 确信每批 $n$ 台 QC 机器中有严格超过一半的机器正常工作，但夜晚只有 $12$ 小时，因此只能进行少量的测试轮次。你能帮助 ICQC 确定哪些 QC 机器出现故障吗？ 例如，考虑下面的示例交互 1。在第四个小时后，每台机器都测试了其他所有机器。对于机器 $1$，只有一台其他机器声称它故障，如果它真的故障，那么至少有 $3$ 台其他机器会声称这一点。对于机器 $4$，只有一台其他机器声称它正常，这意味着机器 $2$ 必定是故障的，因为应该有超过一半的机器正常工作。注意，即使机器 $4$ 是故障的，它在这些特定的测试轮次中仍然恰好产生了正确的响应。

## 交互 输入的第一行包含一个整数 $b$ ($1 \le b \le 500$)，表示接下来的批次数量。每批是独立的。你应该以交互方式处理每批，这意味着你收到的输入将取决于程序的先前输出。 每批的输入第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示该批中的 QC 机器数量。然后交互以轮次进行。在每轮中，你的程序可以通过写一行形式为“$\texttt{test}$ $x_1\ x_2\ \ldots\ x_n$”来安排下一小时的测试，表示每台机器 $i$ 应该对机器 $x_i$ 进行测试。如果 $x_i=0$，则机器 $i$ 在该轮中闲置，不执行测试。序列中的所有正数必须是不同的。 写完这一行后，将有一个结果从输入中读取。结果是一行，包含一个长度为 $n$ 的字符串，在位置 $i$ 上有一个 '$\texttt{1}$' 表示机器 $i$ 认为机器 $x_i$ 正常工作，'$0$' 表示机器 $i$ 认为机器 $x_i$ 故障，和 '-'（破折号）表示机器 $i$ 在该轮中闲置。 当你的程序确定哪些机器故障时，但不晚于 $12$ 轮测试后，它必须写一行形式为“$\texttt{answer}$ $S$”，其中 $S$ 是一个长度为 $n$ 的二进制字符串，位置 $i$ 上有一个 '$\texttt{1}$' 表示机器 $i$ 正常工作，'$0$' 表示它故障。 写完答案行后，你的程序应开始处理下一批，读取其数量 $n$。当所有 $b$ 批次处理完毕后，交互结束，程序应退出。 *交互评估注意事项：* - *评估是非对抗性的，这意味着每台机器测试其他机器的结果是预先选择的，而不是响应你的查询。* - *写完后不要忘记刷新输出缓冲区。有关详细信息，请参阅评估说明附录。* - *为本地测试提供了一个命令行工具，以及对应于示例交互的输入文件。该工具顶部有注释以解释其使用。*

无

题面翻译由 ChatGPT-4o 提供。