题目背景

ICPC2020 WF H

题目描述

Innovative Computable Quality Control (ICQC) has developed a ground-breaking new machine for performing, well, quality control. Thanks to its novel Deep Intelligence technology, an ICQC quality control (QC) machine can automatically, with $100\%$ accuracy, detect manufacturing errors in any machine in existence, whether it is a coffee machine, an intergalactic space ship, or a quantum computer.

ICQC is now setting up its factory for producing these QC machines. Like any other manufacturing process, some fraction of the produced machines will suffer from malfunctions and these need to be found and discarded. Fortunately, ICQC has just the product for detecting malfunctioning machines!

Obviously, ICQC should not simply use a QC machine on itself, since a malfunctioning machine might incorrectly classify itself as working correctly. Instead, ICQC will take each batch of $n$ machines produced during a day and have them test each other overnight. In particular, during every hour of the night, each of the $n$ QC machines can run a check on one of the other QC machines, and simultaneously be checked by one other QC machine.

If the machine running the check is correct, it will correctly report whether the tested machine is correct or malfunctioning, but if the machine running the check is malfunctioning, it may report either result. If a machine A is used to test a machine B multiple times it will return the same result every time, even if machine A is malfunctioning. The exact testing schedule does not have to be fixed in advance, so the choice of which machines should check which other machines during the second hour of the night may be based on the result of the tests from the first hour, and so on.

ICQC are $100\%$ confident that strictly more than a half of the $n$ QC machines in each batch are working correctly, but the night is only $12$ hours long, so there is only time to do a small number of test rounds. Can you help ICQC determine which QC machines are malfunctioning?

For example, consider Sample Interaction 1 below. After the fourth hour, every machine has tested every other machine. For machine $1$, only one other machine claimed that it was malfunctioning, and if it was truly malfunctioning then at least $3$ of the other machines would claim this. For machine $4$, only one other machine claims that it is working, which implies that machine $2$ must be malfunctioning since more than half of the machines are supposed to be working. Note that even though machine $4$ is malfunctioning, it still happened to produce the correct responses in these specific test rounds.

输入格式

Interaction

The first line of input contains a single integer $b$ ($1 \le b \le 500$), the number of batches to follow. Each batch is independent. You should process each batch interactively, which means the input you receive will depend on the previous output of your program.

The first line of input for each batch contains a single integer $n$ ($1 \le n \le 100$), the number of QC machines in the batch. The interaction then proceeds in rounds. In each round, your program can schedule tests for the next hour, by writing a line of the form "$\texttt{test}$ $\ x_1\ x_2\ \ldots\ x_n$" indicating that each machine $i$ should run a test on machine $x_i$. If $x_i=0$, then machine $i$ is idle in that round and performs no test. All positive numbers in the sequence must be distinct.

After writing this line, there will be a result to read from the input. The result is one line containing a string of length $n$, having a '$\texttt{1}$' in position $i$ if machine $i$ says that machine $x_i$ is working correctly, '$\texttt{0}$' if machine $i$ says that machine $x_i$ is malfunctioning, and '$\texttt{-}$' (dash) if machine $i$ was idle in the round.

When your program has determined which machines are malfunctioning, but no later than after $12$ rounds of tests, it must write a line of the form "$\texttt{answer}$ $S$" where $S$ is a binary string of length $n$, having a '$\texttt{1}$' in position $i$ if machine $i$ is working correctly, and a '$\texttt{0}$' if it is malfunctioning.

After writing the answer line, your program should start processing the next batch by reading its number $n$. When all $b$ batches have been processed, the interaction ends and your program should exit.

Notes on interactive judging:

• The evaluation is non-adversarial, meaning that the result of each machine testing each other machine is chosen in advance rather than in response to your queries.
• Do not forget to flush output buffers after writing. See the Addendum to Judging Notes for details.
• You are provided with a command-line tool for local testing, together with input files corresponding to the sample interactions. The tool has comments at the top to explain its use.

题目大意

【题目描述】

创新的可计算质量控制（ICQC）开发了一种开创性的新机器，用于执行良好的质量控制。得益于其新颖的深度智能技术，ICQC 质量控制（QC）机器能够以 $100\%$ 的准确度自动检测现有任何机器的制造错误，无论是咖啡机、星际飞船还是量子计算机。

ICQC 目前正在建立工厂生产这些 QC 机器。像任何其他制造过程一样，生产的机器中有一部分会出现故障，需要找到并丢弃。幸运的是，ICQC 只有检测故障机器的产品！

显然，ICQC 不应该简单地在自己身上使用 QC 机器，因为出现故障的机器可能会错误地将自己归类为正常工作。相反，ICQC 将在一天内生产每批 $n$ 机器，并让它们在一夜之间相互测试。特别是，在夜间的每一个小时，每个 $n$ QC机器都可以在另一台 QC 机器上运行检查，同时由另一台 QC 机器进行检查。

如果运行检查的机器是正确的，它将正确地报告测试机器是正确的还是故障的，但如果运行检查的机器是故障的，它可能会报告任何一个结果。如果使用机器 A 多次测试机器B，即使机器 A 出现故障，每次都会返回相同的结果。准确的测试时间表不必事先确定，因此，在夜间第二个小时，哪些机器应该检查哪些其他机器，可以根据第一个小时的测试结果来选择，以此类推。

ICQC $100\%$ 确信，严格来说，每批 $n$ QC 机器中有一半以上工作正常，但夜间只有$12$ 小时，因此只有时间进行少量测试。您能帮助 ICQC 确定哪些 QC 机器出现故障吗？

例如，考虑下面的样本交互作用 $1$。在第四个小时之后，每台机器都测试了其他每台机器。对于机器 $1$，只有另一台机器声称它有故障，如果它真的有故障，那么其他机器中至少有 $3$ 台会声称这一点。对于机器$4$，只有另一台机器声称它正在工作，这意味着机器 $2$ 一定有故障，因为超过一半的机器应该在工作。请注意，尽管机器 $4$ 出现故障，但在这些特定的测试回合中仍碰巧产生了正确的响应。

【输入格式】

第一行输入包含一个整数 $b$（$1≤ b≤500$），要遵循的批次数。每批都是独立的。您应该以交互方式处理每个批，这意味着您收到的输入将取决于您的程序之前的输出。

每个批次的第一行输入包含一个整数 $n$ （$1≤n≤100$），批次中 QC 机器的数量。然后，交互循环进行。在每一轮中，你的程序都可以通过写一行表格来安排下一个小时的测试 “ $\texttt{test}$ $x_1$ $x_2$ $x_n$”指示每台机器 $i$ 应在机器 $x_i$ 上运行测试。如果 $x_i$ 为 $0$，然后，机器 $i$ 在该轮中处于空闲状态，不执行任何测试。序列中的所有正数必须是不同的。

写下这一行后，将有一个从输入中读取的结果。结果是一行包含长度为 $n$ 的字符串，如果机器 $i$ 表示机器 $x_i$，则在位置 $i$ 处有“$\texttt{1}$”，$x_i$ 工作正常，“$\texttt{0}$” 如果机器 $i$ 显示机器 $x_i$ 出现故障，如果机器 $i$ 在循环中处于空闲状态，则为“$\texttt{-}$”（破折号）。

当您的程序确定哪些机器出现故障时，但不迟于 $12$ 轮测试之后，它必须以“$\texttt{answer}$ $S$”的形式写一行，其中 $S$ 是长度为 $n$ 的二进制字符串，如果机器 $i$ 正常工作，则在位置 $i$ 处有“$\texttt{1}$”，如果机器 $i$ 出现故障，则在位置 $i$ 处有“$\texttt{0}$”。

在写下答案行之后，你的程序应该通过读取下一批的编号 $n$ 来开始处理下一批。当所有 $b$ 批处理完成后，交互结束，程序应该退出。

关于互动评判的说明：

• 评估是非对抗性的，这意味着每台机器测试另一台机器的结果是提前选择的，而不是响应您的查询。
• 写入后不要忘记刷新输出缓冲区。有关详细信息，请参见《评委须知》附录。
• 我们为您提供了一个用于本地测试的命令行工具，以及与示例交互相对应的输入文件。该工具顶部有注释解释其用途。

1
5
10101
01110
10101
10101
10101

test 5 4 2 1 3
test 4 5 1 3 2
test 2 3 4 5 1
test 3 1 5 2 4
answer 10101

2
4
1111
7
0001100
----11-

test 2 3 4 1
answer 1111
test 2 3 4 5 6 7 1
test 0 0 0 0 2 4 0
answer 0101110