这是一个交互问题。您必须在打印每一行后立即使用刷新操作。例如,在 C++ 中,您应该使用函数 fflush(stdout),在 Java 或 Kotlin 中 — System.out.flush(),在 Python 中 — sys.stdout.flush()。
陪审团有一个字符串 $$$s$$$,由字符 0 和/或 1 组成。该字符串的第一个字符是 0。该字符串的长度是 $$$n$$$。你必须猜测这个字符串。让我们将 $$$s[l..r]$$$ 表示为 $$$s$$$ 从 $$$l$$$ 到 $$$r$$$ 的子字符串(即 $$$s[l..r]$$$ 是字符串 $$$s_ls_{l+1} \dots s_r$$$)。
设字符串$$$s$$$的前缀函数为数组$$$[p_1, p_2, \dots, p_n]$$$,其中$$$p_i$$$是[0, i-1]$$$中最大的整数$$$j \,使得$$$s[1..j] = s[i-j+1..i]$$$。另外,令字符串 $$$s$$$ 的反前缀函数为数组 $$$[q_1, q_2, \dots, q_n]$$$,其中 $$$q_i$$$ 是 [0, i-1]$$$ 中的最大整数 $$$j \,使得 $$$s[1..j]$$$ 在每个位置都不同于 $$$s[i-j+1..i]$$$。
例如,对于字符串011001,其前缀函数为$$$[0, 0, 0, 1, 1, 2]$$$,其反前缀函数为$$$[0, 1, 1, 2, 3, 4]$$$。
您可以要求两种类型的查询来猜测字符串 $$$s$$$:
- $$$1$$$ $$$i$$$ — "$$$p_i$$$ 的价值是多少?";
- $$$2$$$ $$$i$$$ — “$$$q_i$$$ 的价值是多少?”。
您必须通过询问不超过 $$$789$$$ 查询来猜测字符串。请注意,给出答案不算作查询。
在每个测试和每个测试用例中,字符串 $$$s$$$ 都是预先固定的。
互动
最初,陪审团程序发送一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
在每个测试用例开始时,陪审团程序发送一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 字符串的长度。
之后,您的程序可以通过打印以下行之一向陪审团程序提交查询(不要忘记在打印一行后刷新输出!):
- $$$1$$$ $$$i$$$ — 查询“$$$p_i$$$ 的值是多少?”;
- $$$2$$$ $$$i$$$ — 查询“$$$q_i$$$ 的值是多少?”。
对于每个查询,陪审团在单独的行上打印一个整数。它是:
- 您的查询的答案,如果查询正确并且您没有超出查询限制;
- 或整数 $$$-1$$$,如果您的查询不正确(例如,不满足约束 $$$1 \le i \le n$$$)或者如果您在处理当前测试用例时询问了太多查询。
要提交答案,您的程序应发送以下格式的一行(不要忘记在打印一行后刷新输出!):
- $$$0$$$ $$$s$$$,其中 $$$s$$$ 是 $$$n$$$ 字符 0 和/或 1 的序列。
如果你的猜测是正确的,陪审团程序将在单独的一行上打印一个整数$$$1$$$,表明你可以继续进行下一个测试用例(或者终止程序,如果它是最后一个测试用例),并且你提出的查询数量被重置。如果不正确,陪审团程序将在单独的一行上打印一个整数 $$$-1$$$。
当你的程序收到 $$$-1$$$ 作为答案后,它应该立即终止。这将导致您提交的内容被判定为“错误答案”。如果您的程序没有终止,则您提交的结论是不确定的。
示例
输入 #1
2 // 2 test cases 6 // n = 6 0 // p[3] = 0 1 // q[2] = 1 4 // q[6] = 4 1 // p[4] = 1 1 // answer is correct 5 // n = 5 1 // p[2] = 1 2 // q[4] = 2 2 // q[5] = 2 1 // answer is correct
输出 #1
1 3 // what is p[3]? 2 2 // what is q[2]? 2 6 // what is q[6]? 1 4 // what is p[4]? 0 011001 // the guess is 011001 1 2 // what is p[2]? 2 4 // what is q[4]? 2 5 // what is q[5]? 0 00111 // the guess is 00111
注意
该示例包含测试中一种可能的交互方式,其中 $$$t = 2$$$,陪审团猜测的字符串是 011001 和 00111。请注意,// 符号后面的所有内容都是注释,解释哪一行在交互中意味着什么。陪审团程序不会在实际问题中打印这些注释,您也不应该打印它们。为了方便起见,还添加了空行,陪审团程序不会打印它们,并且您的解决方案不应打印任何空行。