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 会拿出一天生产的每批 台机器,然后让它们在晚上互相测试。特别地,在晚上的每小时,这 台质量控制机器可以对其他一台质量控制机器进行检查,并同时被一台质量控制机器检查。
如果对其他机器进行检查的机器是没有故障的,那么它会正确地报告被测机是没有故障的还是有故障的,但是如果对其他机器进行检查的机器是有故障的,它会报告两者之一的结果。如果机器 被用来测试机器 多次,即使 是有故障的,它也可能每次都返回一样的结果。实际的测试计划不需要提前确定,因此在晚上的第二小时,选择哪台机器去测试哪台机器可能取决于第一小时的测试结果,以此类推。
ICQC 有 100% 的把握相信在每批 台质量控制机器中,有严格超过一半的机器是正常的,但是晚上只有 小时,因此只有做很少轮数测试的时间。你可以帮助 ICQC 确定哪些质量控制机器是有故障的吗?
例如,考虑下面的样例交互 。在第四个小时之后,所有机器都已经测试了所有其他机器。对于机器 ,只有一台其他的机器称它是有故障的,如果它真的有故障,那么应该有至少 台其它机器会报告它有故障。对于机器 ,只有一台其他的机器称它工作正常,这就暗示了机器 一定是有故障的,因为有一半以上数量的机器应该是没有故障的。注意即使机器 是有故障的,它也可以在某些测试轮次中生成正确的结果。
交互过程
输入的第一行包含一个整数 ,表示接下来测试的批数。每批都是独立的。你应该通过交互处理每批的信息,这意味着你收到的输入取决于你程序之前的输出。
对于每批,输入的第一行包含一个整数 ,表示每批中质量控制机器的个数。之后交互开始。对于每轮,你的程序可以通过输出形如 的行来安排下一小时的测试任务,表示每台机器 需要测试机器 。如果 ,那么机器 本轮会空闲出来,不执行任何测试操作。在数列中所有正整数都必须互不相同。
在本行输出完成后,需要从输入中读取结果。这个结果是一个长度为 的字符串,第 位如果是 ,是指机器 称机器 没有故障,如果是 是指机器 称机器 有故障,如果是 (短横)是指机器 本轮空闲。
当你的程序已经确定了哪些机器是有故障的,并且是在不晚于 轮测试之前确定的,你的程序必须以 这样的形式输出一行,其中 是一个长度为 的 字符串,第 位如果是 ,则表明机器 没有故障,如果是 ,则表示机器 有故障。
在输出答案后,你的程序需要通过读入 ,开始处理下一批机器。当所有 批机器均处理完成后,交互终止,你的程序需要退出。
交互题测评注意事项:
- 交互过程是非对抗性的,这意味着每台机器测试其他机器产生的结果是事先确定的,而不是根据你的询问来确定的。
- 在输出之后不要忘记清理输出缓冲区,也不要忘记输出换行。
- 「文件」区提供了一个命令行工具来做本地调试,同时提供了样例交互的输入文件。在工具的最上方有注释来解释使用方法。
样例交互 1
读取 | 输出 |
---|---|
样例交互 2
读取 | 输出 |
---|---|