一个研究财团为他们的新数据中心建立了一个新的数据库系统。该数据库由一台主计算机和 $N$ 台工作计算机组成,工作计算机的 ID 从 $0$ 到 $N-1$。每台工作计算机恰好存储一位信息……这看起来相当浪费,但这些数据非常重要!
你受雇评估该数据库的以下指令:
TEST_STORE <bits>:主计算机读入 <bits>(一个长度为 $N$ 的位串),并将第 $i$ 位发送给第 $i$ 台工作计算机进行存储。随后,主计算机将从工作计算机中读回这些位,并按读入时的顺序返回给用户。
在正常运行情况下,TEST_STORE 应该返回与读入相同的位串,但不幸的是,有 $B$ 台工作计算机损坏了!
损坏的工作计算机能够正确存储分配给它们的位,但每当主计算机尝试从损坏的工作计算机读取数据时,都不会返回任何位。这导致 TEST_STORE 操作仅返回 $N-B$ 位,即存储在未损坏工作计算机上的位(按其 ID 的升序排列)。例如,假设 $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 调用来找出哪些工作计算机损坏了。
输入格式
这是一个交互式问题。请确保你已阅读我们 FAQ 中关于交互式问题的相关信息。
程序首先应读取包含单个整数 $T$ 的单行,表示测试用例的数量。然后,你需要处理 $T$ 个测试用例。
对于每个测试用例,程序首先读取包含三个整数 $N$、$B$ 和 $F$ 的单行,分别表示工作计算机的数量、损坏的工作计算机数量,以及你可以发送的行数(如下所述)。
然后,你可以向评测机发送最多 $F$ 行,每行包含一个长度恰好为 $N$ 的字符串,由 0 或 1 组成。每次发送一行时,评测机都会检查你是否进行了超过 $F$ 次调用。如果超过了,评测机将发送包含单个 -1 的单行,然后结束所有通信并等待你的程序结束。否则,评测机将发送一个长度为 $N-B$ 的字符串:即 TEST_STORE 返回的字符串,如上所述。
一旦你的程序知道了 $B$ 台损坏工作计算机的索引,就可以通过发送 $B$ 个空格分隔的整数来结束该测试用例:即损坏工作计算机的 ID,按升序排列。这不计入你的 $F$ 次调用。
如果这 $B$ 个整数不是损坏工作计算机的准确 ID,你将收到 Wrong Answer 判决,评测机将发送包含 -1 的单行,之后不再进行任何通信。如果你的答案正确,评测机将发送包含 1 的单行,随后是下一测试用例的起始行(如果是最后一个测试用例,则退出)。
数据范围
时间限制:每个测试集 20 秒。 内存限制:1GB。 $1 \le T \le 100$。 $2 \le N \le 1024$。 $1 \le B \le \min(15, N-1)$。
测试集 1(可见)
$F = 10$。
测试集 2(隐藏)
$F = 5$。
样例
样例交互
以下交互满足测试集 1 的限制。
t = readline_int() // 读取 2 到 t n, b, f = readline_int_list() // 读取 5, 2, 10 到 n, b, f printline 01101 to stdout // 接下来的四次输出与题目描述中的示例匹配 flush stdout response = readline_str() // 读取 111 到 response。(此时,我们可以确定答案;剩余的查询仅为示例!) printline 00110 to stdout flush stdout response = readline_str() // 读取 010 到 response printline 01010 to stdout flush stdout response = readline_str() // 读取 100 到 response printline 11010 to stdout flush stdout response = readline_str() // 读取 100 到 response printline 0 3 to stdout // 猜测答案。注意我们不需要使用所有 10 次允许的查询。 flush stdout verdict = readline_int() // 读取 1 到 verdict。我们答对了该测试用例! n, b, f = readline_int_list() // 读取 2, 1, 10 到 n, b, f printline 01 to stdout // 01 是一个查询,而不是对最终答案的猜测(如果我们想猜测只有 1 号工作计算机损坏,我们必须像下面那样发送 1) flush stdout response = readline_str() // 读取 1 到 response printline 1 to stdout // 进行了一个(错误的)盲猜 verdict = readline_str() // 读取 -1 到 verdict exit // 退出以避免模糊的 TLE 错误