loj#P6797. 「ICPC World Finals 2020」QC QC

「ICPC World Finals 2020」QC QC

题目描述

创新可计算质量控制(Innovative Computable Quality Control, ICQC)开发了一种突破性的新机器,用于进行良好的质量控制。由于它使用了新颖的深度智能技术,一台 ICQC 质量控制(QC)器可以以 100% 的准确率,全自动地探测任何现有的机械中出现的制造错误,无论这个机械是咖啡机,星际飞船还是量子计算机。

ICQC 现在正在搭建工厂来制造这些质量控制机器。就像其他制造过程一样,一些生产的机器可能会出现故障,这些机器需要找出来并丢弃。幸运的是,ICQC 正是探测出现故障的机器的产品。

显然,ICQC 不能简单地对产品本身使用质量控制机器,因为机器的故障可能会导致机器本身将自己归为没有故障的一类。作为替代,ICQC 会拿出一天生产的每批 nn 台机器,然后让它们在晚上互相测试。特别地,在晚上的每小时,这 nn 台质量控制机器可以对其他一台质量控制机器进行检查,并同时被一台质量控制机器检查。

如果对其他机器进行检查的机器是没有故障的,那么它会正确地报告被测机是没有故障的还是有故障的,但是如果对其他机器进行检查的机器是有故障的,它会报告两者之一的结果。如果机器 AA 被用来测试机器 BB 多次,即使 AA 是有故障的,它也可能每次都返回一样的结果。实际的测试计划不需要提前确定,因此在晚上的第二小时,选择哪台机器去测试哪台机器可能取决于第一小时的测试结果,以此类推。

ICQC 有 100% 的把握相信在每批 nn 台质量控制机器中,有严格超过一半的机器是正常的,但是晚上只有 1212 小时,因此只有做很少轮数测试的时间。你可以帮助 ICQC 确定哪些质量控制机器是有故障的吗?

例如,考虑下面的样例交互 11。在第四个小时之后,所有机器都已经测试了所有其他机器。对于机器 11,只有一台其他的机器称它是有故障的,如果它真的有故障,那么应该有至少 33 台其它机器会报告它有故障。对于机器 44,只有一台其他的机器称它工作正常,这就暗示了机器 22 一定是有故障的,因为有一半以上数量的机器应该是没有故障的。注意即使机器 44 是有故障的,它也可以在某些测试轮次中生成正确的结果。

交互过程

输入的第一行包含一个整数 b (1b500)b\ (1\le b\le 500),表示接下来测试的批数。每批都是独立的。你应该通过交互处理每批的信息,这意味着你收到的输入取决于你程序之前的输出。

对于每批,输入的第一行包含一个整数 n (1n100)n\ (1\le n\le 100),表示每批中质量控制机器的个数。之后交互开始。对于每轮,你的程序可以通过输出形如 test x1 x2xn\texttt{test}\ x_1\ x_2\ldots x_n 的行来安排下一小时的测试任务,表示每台机器 ii 需要测试机器 xix_i。如果 xi=0x_i=0,那么机器 ii 本轮会空闲出来,不执行任何测试操作。在数列中所有正整数都必须互不相同。

在本行输出完成后,需要从输入中读取结果。这个结果是一个长度为 nn 的字符串,第 ii 位如果是 1\texttt 1,是指机器 ii 称机器 xix_i 没有故障,如果是 0\texttt 0 是指机器 ii 称机器 xix_i 有故障,如果是 -\texttt -(短横)是指机器 ii 本轮空闲。

当你的程序已经确定了哪些机器是有故障的,并且是在不晚于 1212 轮测试之前确定的,你的程序必须以 answer S\texttt{answer}\ S 这样的形式输出一行,其中 SS 是一个长度为 nn0101 字符串,第 ii 位如果是 1\texttt 1,则表明机器 ii 没有故障,如果是 0\texttt 0,则表示机器 ii 有故障。

在输出答案后,你的程序需要通过读入 nn,开始处理下一批机器。当所有 bb 批机器均处理完成后,交互终止,你的程序需要退出。

交互题测评注意事项:

  • 交互过程是非对抗性的,这意味着每台机器测试其他机器产生的结果是事先确定的,而不是根据你的询问来确定的。
  • 在输出之后不要忘记清理输出缓冲区,也不要忘记输出换行。
  • 「文件」区提供了一个命令行工具来做本地调试,同时提供了样例交互的输入文件。在工具的最上方有注释来解释使用方法。

样例交互 1

读取 输出
11
55
test 5 4 2 1 3\texttt{test 5 4 2 1 3}
11011\texttt{11011}
test 4 5 1 3 2\texttt{test 4 5 1 3 2}
00110\texttt{00110}
test 2 3 4 5 1\texttt{test 2 3 4 5 1}
01011\texttt{01011}
test 3 1 5 2 4\texttt{test 3 1 5 2 4}
10100\texttt{10100}
answer 10101\texttt{answer 10101}

样例交互 2

读取 输出
22
44
test 2 3 4 1\texttt{test 2 3 4 1}
1111\texttt{1111}
answer 1111\texttt{answer 1111}
77
test 2 3 4 5 6 7 1\texttt{test 2 3 4 5 6 7 1}
0001100\texttt{0001100}
test 0 0 0 0 2 4 0\texttt{test 0 0 0 0 2 4 0}
----11-\texttt{----11-}
answer 0101110\texttt{answer 0101110}