← 返回题目列表

Codeforces · 2038/G

G. 猜一个字

中文机器翻译题面 查看原题

这是一个交互问题。您必须在打印每一行后立即使用刷新操作。例如,在 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。请注意,// 符号后面的所有内容都是注释,解释哪一行在交互中意味着什么。陪审团程序不会在实际问题中打印这些注释,您也不应该打印它们。为了方便起见,还添加了空行,陪审团程序不会打印它们,并且您的解决方案不应打印任何空行。