← 返回题目列表

Codeforces · 1697/D

D. 猜字符串

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

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

陪审团选择了由 $$$n$$$ 个字符组成的字符串 $$$s$$$; $$$s$$$ 的每个字符都是小写拉丁字母。你的任务是猜测这个字符串;最初,您只知道它的长度。

您可能会提出两种类型的疑问:

- $$$1$$$ $$$i$$$ — 第一种类型的查询,其中 $$$i$$$ 是从 $$$1$$$ 到 $$$n$$$ 的整数。针对此询问,陪审团将告诉您角色 $$$s_i$$$;
- $$$2$$$ $$$l$$$ $$$r$$$ — 第二种类型的查询,其中 $$$l$$$ 和 $$$r$$$ 是整数,使得 $$$1 \le l \le r \le n$$$。针对此查询,陪审团将告诉您 $$$s_l、s_{l+1}、\dots、s_r$$$ 之间不同字符的数量。

您可以提出不超过 $$$26$$$ 的第一类型查询,以及不超过 $$$6000$$$ 的第二类型查询。您的任务是恢复字符串$$$s$$$。

对于此问题中的每个测试,字符串 $$$s$$$ 都是预先固定的,并且对于每次提交都是相同的。

输入

最初,陪审团程序在单独的行上发送一个整数 $$$n$$$ — $$$s$$$ 的大小 ($$$1 \le n \le 1000$$$)。

互动

要提出查询,您应该使用以下格式之一发送包含查询的一行:

- ? 1 i — 对于第一种类型的查询 ($$$1 \le i \le n$$$);
- ? 2 l r — 用于第二类型的查询 ($$$1 \le l \le r \le n$$$)。

发送查询行后不要忘记刷新输出。

您的查询的答案将在单独的行中给出。对于第一种类型的查询,答案将是字符 $$$s_i$$$。对于第二种类型的查询,答案将是一个整数,等于$$$s_l、s_{l+1}、\dots、s_r$$$中不同字符的数量。

您可以提出不超过 $$$26$$$ 的第一类型查询,以及不超过 $$$6000$$$ 的第二类型查询。

如果您询问太多问题,或者陪审团程序无法识别您的询问格式,您的询问的答案将是一个整数 $$$0$$$。收到 $$$0$$$ 作为答案后,您的程序应立即终止 - 否则您可能会收到“运行时错误”、“超出时间限制”或其他一些判断,而不是“错误答案”。

输出

要给出答案,请打印一行! s 末尾换行,其中 $$$s$$$ 应该是陪审团选出的字符串。之后,您的程序应该刷新输出并正常终止。

示例

输入 #1

5
4
u
2
g
e
s
1

输出 #1

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

注意

我们来分析一下交互的例子。

陪审团选择的字符串是猜测的,因此陪审团最初发送一个整数 $$$5$$$。

1.第一个查询是? 2 1 5,意思是“统计$$$s_1, s_2, \dots, s_5$$$中不同字符的个数”。答案是$$$4$$$。
2.第二个查询是? 1 2,意思是“告诉$$$s_2$$$是哪个字符”。答案是你。
3.第三个查询是? 2 1 2,表示“统计$$$s_1$$$和$$$s_2$$$之间不同字符的个数”。答案是$$$2$$$。
4.第四个查询是? 1 1,意思是“告诉$$$s_1$$$是哪个字符”。答案是g。
5.第五个查询是? 1 3,意思是“告诉$$$s_3$$$是哪个字符”。答案是e。
6.第六个查询是? 1 4,意思是“告诉哪个字符是$$$s_4$$$”。答案是 s。
7.第七个查询是? 2 4 5,意思是“统计$$$s_4$$$和$$$s_5$$$之间不同字符的个数”。答案是$$$1$$$,因此可以推断$$$s_4$$$ 与$$$s_5$$$ 相同。

最后,答案提交为!猜测,并且推导正确。