← 返回题目列表

Codeforces · 1282/D

D. 魔法神器

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

这是一个交互问题。

完成魔法神庙的最后一个关卡后,你获得了第 255 级的强大神器。不要急于庆祝,因为这个神器有一个强大的符文,可以用一个咒语 $$$s$$$ 摧毁它,你将会找到它。

我们将拼写定义为仅由字母 a 和 b 组成的非空字符串。

你可以随时施展任意非空法术$$$t$$$,神器上的符文将开始抵抗。符文的抗性是指定施放法术 $$$t$$$ 和破坏符文的法术 $$$s$$$ 的字符串之间的编辑距离。

两个字符串$$$s$$$和$$$t$$$的编辑距离是一个值,等于对$$$s$$$进行替换、插入、删除字符的单字符操作的最少次数,得到$$$t$$$。例如,ababa 和 aaa 之间的距离为 $$$2$$$,aaa 和 aba 之间的距离为 $$$1$$$,bbaba 和 abb 之间的距离为 $$$3$$$。当且仅当字符串相等时,编辑距离为 $$$0$$$。

还值得考虑的是,该神器具有抵抗力限制 - 如果您施放超过 $$$n + 2$$$ 法术(其中 $$$n$$$ 是法术 $$$s$$$ 的长度),符文将被阻挡。

因此,需要 $$$n + 2$$$ 或更少的法术来摧毁你神器上的符文。请记住,所需的破坏性法术 $$$s$$$ 也必须计入这些 $$$n + 2$$$ 法术中。

请注意,你事先并不知道符文破坏法术 $$$s$$$ 的长度 $$$n$$$。只知道它的长度$$$n$$$不超过$$$300$$$。

互动

交互是通过查询进行的。

每个请求都包含一个非空字符串 $$$t$$$ — 您要施展的咒语。字符串$$$t$$$的长度不应超过$$$300$$$。每个字符串应仅包含字母 a 和 b。

作为对查询的响应,您将获得阻力符文 - 指定施放咒语 $$$t$$$ 和秘密符文破坏咒语 $$$s$$$ 的字符串之间的编辑距离。请记住,$$$s$$$ 仅包含字母 a 和 b。

打破符文后,你的程序应该立即结束。当您收到抵抗 $$$0$$$ 的响应时,符文就会被摧毁。收到值 $$$0$$$ 后,您的程序应该正常终止。

在这个问题中,交互器不具有自适应性。这意味着在任何测试期间,符文破坏咒语 $$$s$$$ 不会改变。

如果您的查询无效,将返回-1。收到此消息后,您的程序应立即正常终止(例如,通过调用 exit(0)),否则,测试系统可能会发出任意判决。

如果咒语数量超过限制($$$n + 2$$$,其中 $$$n$$$ 是咒语 $$$s$$$ 的长度,您不知道),您将得到错误答案判决。

如果您不输出任何内容或忘记刷新输出缓冲区,您的解决方案可能会收到超出空闲限制的判决。

要刷新输出缓冲区,您需要在打印查询和行结束后立即执行以下操作:

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

黑客

对于 hack,请使用以下格式:

在一行中打印字母 a 和 b 的字符串 $$$s$$$ ($$$1 \le |s| \le 300$$$),它定义了符文破坏咒语。

被黑的解决方案将无法直接访问未知咒语。

示例

输入 #1

2

2

1

2

3

0

输出 #1

aaa

aaab

abba

bba

abaaa

aabba