← 返回题目列表

Codeforces · 1286/C2

C2. 疯人院(困难版)

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

这个问题与简单版本的不同之处仅在于总答案长度的限制

这是一个交互问题

Venya 参加了疯人院之旅,其中护理人员与病人玩以下游戏。勤务兵选择一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含小写英文字母。玩家可以提出两种类型的查询:

- ? l r – 要求列出 $$$s[l..r]$$$ 的所有子字符串。子字符串将以随机顺序返回,并且在每个子字符串中,所有字符将被随机打乱。
- ! s – 猜测勤务兵挑选的绳子。该查询只能被询问一次,之后游戏就会结束。如果猜对了字符串,玩家就赢了,否则就输了。

玩家最多可以提出 $$$3$$$ 的第一类查询。

为了方便勤务人员,还有一个额外的限制:第一类所有查询返回的子字符串总数不得超过$$$\left\lceil 0.777(n+1)^2 \right\rceil$$$($$$\lceil x \rceil$$$ 为$$$x$$$ 向上取整)。

Venya 要求你编写一个程序,该程序将通过与勤务人员的程序交互并按照游戏规则行事来猜测字符串。

在使用第二种类型的查询猜测字符串后,您的程序应立即终止。如果你的程序猜错了字符串,或者违反了游戏规则,它将收到错误答案的判决。

请注意,在每个测试用例中,字符串都是预先固定的,并且在游戏过程中不会改变,这意味着交互器不具有自适应性。

输入

第一行包含数字 $$$n$$$ ($$$1 \le n \le 100$$$) — 所选字符串的长度。

互动

您可以通过读取数字 $$$n$$$ 来开始交互。

要查询从 $$$l$$$ 到 $$$r$$$ 的子字符串($$$1 \le l \le r \le n$$$),您应该输出

?左

单独一行。此后,$$$s[l..r]$$$ 的所有子字符串将以随机顺序返回,每个子字符串恰好出现一次。在每个返回的子字符串中,所有字符都将被随机打乱。

在这种情况下,如果您提出错误的查询,请提出超过 $$$3$$$ 的第一类型查询,否则总共返回的子字符串将超过 $$$\left\lceil 0.777(n+1)^2 \right\rceil$$$ 个,您将收到错误答案。

要猜测字符串 $$$s$$$,您应该输出

! s

在单独的一行上。

打印每个查询后,不要忘记刷新输出。否则,您将超出空闲限制。要刷新输出,您可以使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

如果您收到 -(破折号)作为任何查询的答案,则需要使用退出代码 0 终止程序(例如,通过调用 exit(0))。这意味着交互协议中存在错误。如果您不以退出代码 0 终止,您可能会收到任何不成功的判决。

黑客格式

要破解解决方案,请使用以下格式:

第一行应包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串的长度,接下来的行应包含字符串 $$$s$$$。

示例

输入 #1

4

a
aa
a

cb
b
c

c

输出 #1

? 1 2

? 3 4

? 4 4

! aabc