这是一个交互问题。您必须在打印每一行后立即使用刷新操作。例如,在 C++ 中,您应该使用函数 fflush(stdout) 或 cout.flush(),在 Java 或 Kotlin 中 — System.out.flush(),在 Python 中 — sys.stdout.flush()。
陪审团有一个由字符 0 和/或 1 组成的字符串 $$$s$$$。该字符串的长度为 $$$n$$$。
您可以提出以下疑问:
- $$$1$$$ $$$t$$$ — “$$$t$$$ 作为连续子字符串在 $$$s$$$ 中出现了多少次?”这里,$$$t$$$应该是由字符0和/或1组成的字符串;它的长度应至少为$$$1$$$,至多为$$$n$$$。例如,如果字符串 $$$s$$$ 为 111011,字符串 $$$t$$$ 为 11,则查询的响应为 $$$3$$$。
您必须通过询问不超过 $$$3$$$ 查询来猜测字符串 $$$s$$$ 中的至少一个字符。请注意,给出答案不算作查询。
在每个测试和每个测试用例中,字符串 $$$s$$$ 都是预先固定的。
互动
最初,陪审团程序发送一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
在每个测试用例开始时,陪审团程序发送一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 字符串的长度。
之后,您的程序可以通过打印以下行向陪审团程序提交查询(不要忘记在打印一行后刷新输出!):
- $$$1$$$ $$$t$$$ 表示询问“$$$t$$$ 作为连续子字符串在 $$$s$$$ 中出现了多少次?”
对于每个查询,陪审团在单独的行上打印一个整数。它是:
- 您的查询的答案,如果查询正确,并且您没有超出查询限制;
- 或整数 $$$-1$$$,如果您的查询不正确(例如,不满足约束 $$$1 \le |t| \le n$$$ 或字符串 $$$t$$$ 包含 0 和 1 以外的字符),或者如果您在处理当前测试用例时询问了太多查询。
要提交答案,您的程序应发送以下格式的一行(不要忘记在打印一行后刷新输出!):
- $$$0$$$ $$$i$$$ $$$c$$$,其中 $$$1 \le i \le n$$$ 和 $$$c$$$ 为 0 或 1,表示 $$$s_i = c$$$。
如果你的猜测是正确的,陪审团程序将在单独的一行上打印一个整数$$$1$$$,表明你可以继续进行下一个测试用例(或者终止程序,如果它是最后一个测试用例),并且你提出的查询数量被重置。如果不正确,陪审团程序将在单独的一行上打印一个整数 $$$-1$$$。
当你的程序收到 $$$-1$$$ 作为响应后,它应该立即终止。这将导致您提交的内容被判定为“错误答案”。如果您的程序没有终止,则您提交的结论是不确定的。
示例
输入 #1
3 // 3 test cases 3 // the length of the string is 3 1 // 101 occurs once 1 // guessed correctly 2 // the length of the string is 2 0 // 00 occurs zero times 0 // 0 occurs zero times 1 // guessed correctly 2 // the length of the string is 2 1 // 1 occurs once 0 // 01 occurs zero times 1 // guessed correctly
输出 #1
1 101 // how many times 101 occurs 0 2 0 // guess: s[2] is 0 1 00 // how many times 00 occurs 1 0 // how many times 0 occurs 0 1 1 // guess: s[1] is 1 1 1 // how many times 1 occurs 1 01 // how many times 01 occurs 0 2 0 // guess: s[2] is 0
注意
在示例中,有 $$$3$$$ 测试用例:101、11 和 10。请注意,// 符号后面的所有内容都是注释,解释哪一行在交互中意味着什么。陪审团程序不会在实际问题中打印这些注释,您也不应该打印它们。为了方便起见,还添加了空行,陪审团程序不会打印它们,并且您的解决方案不应打印任何空行。