← 返回题目列表

Codeforces · 1117/E

E. 破译字符串

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

这是一个交互问题。请记住在与测试程序通信时刷新输出。您可以在 C++ 中使用 fflush(stdout)、Java 中的 system.out.flush()、Python 中的 stdout.flush() 或 Pascal 中的lush(output) 来刷新输出。如果您使用其他编程语言,请查阅其文档。您还可以参考交互问题指南:https://codeforces.com/blog/entry/45307。

给你一个字符串 $$$t$$$,由 $$$n$$$ 小写拉丁字母组成。该字符串的加密方式如下:最初,陪审团有一个由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。然后他们应用了一系列不超过$$$n$$$(可能为零)的操作。第 $$$i$$$ 操作由两个整数 $$$a_i$$$ 和 $$$b_i$$$ 表示($$$1 \le a_i, b_i \le n$$$),意味着交换索引为 $$$a_i$$$ 和 $$$b_i$$$ 的字符串的两个元素。所有操作均按照它们在序列中放置的顺序完成。例如,如果 $$$s$$$ 是 xyz 并且 $$$2$$$ 执行以下操作:$$$a_1 = 1, b_1 = 2$$$; $$$a_2 = 2, b_2 = 3$$$,那么第一次操作后当前字符串是yxz,第二次操作后当前字符串是yzx,所以$$$t$$$是yzx。

系统会要求您恢复原始字符串$$$s$$$。不幸的是,您没有有关算法中使用的操作的信息(您甚至不知道序列中是否有任何操作)。但是,您可以对任何您想要的字符串运行相同的操作序列,前提是该字符串仅包含小写拉丁字母且其长度为 $$$n$$$,并在这些操作之后获得结果字符串。

你能猜出原始字符串 $$$s$$$ 要求测试系统运行交换序列不超过 $$$3$$$ 次吗?

字符串 $$$s$$$ 和交换顺序在每次测试中都是固定的;交互器不会尝试使测试适应您的解决方案。

输入

最初,测试系统发送一个字符串 $$$t$$$,由小写拉丁字母组成 ($$$1 \le |t| = n \le 10^4$$$)。

互动

在给出答案之前,您最多可以提交 $$$3$$$ 的查询。要提出查询,请按以下格式打印一行:$$$?$$$ $$$s'$$$,其中 $$$s'$$$ 应该是由精确的 $$$n$$$ 小写拉丁字母组成的字符串。该行应以换行符结束。提交查询后,刷新输出并读取查询的答案 - 由 $$$n$$$ 小写拉丁字母组成的字符串 $$$t'$$$,这是将交换序列应用于字符串 $$$s'$$$ 的结果。该字符串将在以换行符结尾的单独行中给出。

如果您提交了错误的查询(或询问超过 $$$3$$$ 查询),则其答案将是一个字符串 0。收到这样的答案后,您的程序应立即终止 - 否则您可能会收到“运行时错误”、“超出时间限制”或其他一些判断,而不是“错误答案”。

输出

为了给出答案,你的程序应该打印一行 $$$!$$$ $$$s$$$ 并在最后换行。之后,它应该刷新输出并正常终止。

示例

输入 #1

yzx
aab
baa
aba

输出 #1

? baa
? aba
? aab
! xyz

注意

在示例中,使用了语句中描述的测试用例。参与者使用字符串 baa 提出第一个查询,该字符串被转换为 aab。第二个查询包含字符串 aba,该字符串已转换为 baa。第三个查询包含字符串 aab,该字符串被转换为 aba。参与者可以推断出初始字符串 $$$s$$$ 是 xyz。

黑客阶段注意事项:

要在黑客阶段提交测试,您应该按以下格式提供:

第一行应包含您猜测的字符串 $$$s$$$,由 $$$n \in [1, 10000]$$$ 小写拉丁字母组成。

第二行应包含 $$$k$$$ ($$$0 \le k \le n$$$) — 序列中交换操作的数量。

然后 $$$k$$$ 行应该跟随,其中 $$$i$$$ 应该表示第 $$$i$$$ 与两个整数 $$$a_i$$$ 和 $$$b_i$$$ 的操作($$$1 \le a_i, b_i \le n$$$)。

例如,示例测试如下所示:

xyz

2

1 2

2 3