#P15874. [Roi2023 Team]Guess the String猜字符串

    ID: 15085 交互题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-自适应查询信息量划分不变量分析状态机模拟

[Roi2023 Team]Guess the String猜字符串

猜字符串

题目背景

这是一道交互式题目。

评测程序想好了一个长度为 nn 的字符串 ss,字符串只由字符 a、b、c 组成。你的程序需要猜出这个字符串。

为了猜出字符串,你的程序可以进行若干次询问。每次询问包含一个整数 ii 和一个长度为 22 的小写英文字母串 uu。评测程序会回答下面两个命题中有多少个为真:

si=u1,si+1=u2.s_i=u_1,\qquad s_{i+1}=u_2.

也就是说,回答可能是 0,1,20,1,2。

你需要在不超过

⌈4n3⌉\left\lceil \frac{4n}{3}\right\rceil

次询问内猜出字符串。这里 ⌈x⌉\lceil x\rceil 表示向上取整。

交互协议

本题一次程序运行中可能包含多局游戏。保证每次运行的游戏数量不超过 100100。

每局游戏开始时,你的程序需要从标准输入读入一个整数 nn。

  • 若 n=0n=0,表示所有游戏已经结束,你的程序应当立刻退出;
  • 否则,表示新一局游戏开始,隐藏字符串长度为 nn,其中 2≤n≤1002\le n\le 100。

在一局游戏中,你的程序可以进行不超过 ⌈4n3⌉\left\lceil \frac{4n}{3}\right\rceil 次询问。

询问

若要进行一次询问,输出一行:

? i u

其中:

  • 1≤i≤n−11\le i\le n-1;
  • uu 是一个长度为 22 的小写英文字母串。

随后,你的程序需要从标准输入读入一个整数 aa,其中 a∈{0,1,2}a\in\{0,1,2\},表示下面两个命题中成立的个数:

si=u1,si+1=u2.s_i=u_1,\qquad s_{i+1}=u_2.

回答

当你的程序已经确定隐藏字符串后,输出一行:

! s

其中 ss 是你猜出的长度为 nn 的字符串。

输出最终答案不计入询问次数。输出答案后,你的程序应继续读取下一局游戏的 nn,直到读到 n=0n=0 为止。

重要说明

评测程序可以是自适应的。也就是说,它不一定在一开始固定一个字符串,而是可以根据你的询问动态选择回答,只要始终存在至少一个字符串与此前所有回答一致即可。

因此,如果你的程序输出的字符串不是评测程序最终认可的那个字符串,即使它也可能与部分回答一致,也可能得到 Wrong Answer。

每次输出询问或答案后,都必须换行并刷新输出缓冲区。C++ 中可以使用 endl,或者输出 \n 后调用 cout.flush()。

样例

标准输入

3

2

1

1

2

0

标准输出

? 1 ab

? 2 ba

? 2 bb

? 2 bc

! abc

样例说明

样例中的空行只是为了更清楚地展示交互过程。真实交互中不会有这些空行,你也不应该输出空行。每次询问、每次回答后输出一个换行即可。

数据范围

  • 2≤n≤1002\le n\le 100;
  • 每次运行的游戏数量不超过 100100;
  • 每局最多允许 ⌈4n3⌉\left\lceil \frac{4n}{3}\right\rceil 次询问。