← 返回题目列表

Codeforces · 1292/E

E. 凛与未知之花

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

这是一个交互问题!

一个平常的日子,在 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

注意

请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。