这是一个交互问题!
一个平常的日子,在 A.R.C. 的隐藏办公室里。马克兰-N,凛收到了一件神器,是探险船长萨加尔送给她的。
经过大量分析,她现在意识到这件神器包含有关一种奇怪的花的数据,这种花早在新时代之前就已经存在了。然而,有关其化学结构的信息已被严格加密。
这种花的化学结构可以表示为字符串$$$p$$$。从包含的未加密文件中,Rin 已经知道该字符串的长度 $$$n$$$,并且她还可以得出结论,该字符串最多包含三个不同的字母:“C”(如碳)、“H”(如氢)和“O”(如氧)。
在每个时刻,Rin 都可以将任意长度的字符串 $$$s$$$ 输入到工件的终端中,并且它将返回 $$$s$$$ 的每个起始位置作为 $$$p$$$ 的子字符串。
然而,该神器的能量有限,无法以任何方式充电,因为该技术太古老,并且与任何当前 A.R.C. 的设备都不兼容。具体来说:
- 该神器仅包含 $$$\frac{7}{5}$$$ 单位的能量。
- 每次 Rin 输入长度为 $$$t$$$ 的字符串 $$$s$$$ 时,工件会消耗 $$$\frac{1}{t^2}$$$ 单位的能量。
- 如果能量低于零,任务将立即被视为失败,因为神器将永远变黑。
由于神器如此珍贵却又脆弱,凛非常紧张地试图破解最终数据。你能向她伸出援助之手吗?
互动
交互以单个整数 $$$t$$$ ($$$1 \le t \le 500$$$) 开始,即测试用例的数量。每个测试用例的交互描述如下:
首先读取一个整数$$$n$$$ ($$$4 \le n \le 50$$$),字符串$$$p$$$的长度。
然后,您可以进行“? s”类型的查询($$$1 \le |s| \le n$$$)来查找 $$$s$$$ 作为 $$$p$$$ 的子字符串出现的情况。
查询后,您需要将其结果读取为一行中的一系列整数:
- 第一个整数 $$$k$$$ 表示 $$$s$$$ 作为 $$$p$$$ 的子字符串出现的次数 ($$$-1 \le k \le n$$$)。如果 $$$k = -1$$$,则意味着您已超出能量限制或打印了无效查询,您需要立即终止,以保证“错误答案”的判决,否则您可能会得到任意判决,因为您的解决方案将继续从关闭的流中读取。
- 以下 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_1 < a_2 < \ldots < a_k \le n$$$) 表示与字符串 $$$s$$$ 匹配的子字符串的起始位置。
当找到字符串$$$p$$$时,打印“!$$$p$$$”来完成一个测试用例。该查询不消耗任何能量。交互器将返回一个整数 $$$1$$$ 或 $$$0$$$。如果交互器返回$$$1$$$,您可以继续下一个测试用例,或者如果它是最后一个测试用例则终止程序。
如果交互器返回 $$$0$$$,则意味着您的猜测不正确,您应该终止以保证“答案错误”的判决。
请注意,在每个测试用例中,字符串 $$$p$$$ 都是预先固定的,并且在查询期间不会改变,即交互器不具有自适应性。
打印任何查询后,不要忘记打印行尾并刷新输出。否则,您可能会超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
对于 hack,请使用以下格式。请注意,您只能使用一个测试用例进行破解:
第一行应包含单个整数 $$$t$$$ ($$$t = 1$$$)。
第二行应包含一个整数 $$$n$$$ ($$$4 \le n \le 50$$$) — 字符串的大小。
第三行应包含大小为 $$$n$$$ 的字符串,仅包含字符“C”、“H”和“O”。这是参赛者必须找出的字符串。
示例
输入 #1
1 4 2 1 2 1 2 0 1
输出 #1
? C ? CH ? CCHO ! CCHH
输入 #2
2 5 0 2 2 3 1 8 1 5 1 5 1 3 2 1 2 1
输出 #2
? O ? HHH ! CHHHH ? COO ? COOH ? HCCOO ? HH ! HHHCCOOH
注意
请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。