4251. Sequence

单点时限: 3.0 sec

内存限制: 512 MB

本题为交互题。

有一个未知的字符串 $S$,它的字符集是 ${\text{a,b,c}}$,它的长度在 $[L,R]$ 中,其中 $L,R$ 是给定的常数。

为了猜出这个字符串 $S$,你可以进行如下询问:

  • 你需要给定一个长度不超过 $R$ 的,字符集为 ${\text{a,b,c}}$ 的字符串 $T$;
  • 交互库会返回:$T$ 是否是 $S$ 的一个子序列(不必连续)。

设 $S$ 的实际长度为 $n$,你只能进行不超过 $\lfloor k\times n\rfloor$ 次询问,其中 $k$ 是给定的实数。

输入格式

第一行:两个整数 $L,R$ 和一个浮点数 $k$。

接下来,对于你的每组询问,交互库将会输出 $0$ 或 $1$,你需要将它输入,为 $1$ 表示你询问的 $T$ 是 $S$ 的子序列,否则表示不是;

输出格式

如果你要提出一次询问,以 ? T 的格式输出,其中 $T$ 是你想询问的字符串。

如果你确定了 $S$,请以 ! S 的格式输出。输出之后,请你立即结束程序。

请注意,你需要在每输出一行之后执行 flush 操作,否则你提交的程序有可能会被判定为 Idleness limit exceeded。适用于各种语言的 flush 函数如下:

  • 对于 C++ 语言,你可以使用 fflush(stdout)
  • 对于 Java 语言,你可以使用 System.out.flush()
  • 对于 Pascal 语言,你可以使用 flush(output)
  • 对于 Python 语言,你可以使用 sys.stdout.flush()

样例

Input
2 2 100.0

0

1
Output

? ac

? ab

! ab

提示

Subtask 1($10$ 分):$L=12,\ R=12,\ k=50000.0$;

Subtask 2($20$ 分):$L=100,\ R=100,\ k=1000.0$,$S$ 中不包含字符 $\text{c}$;

Subtask 3($10$ 分):$L=100,\ R=200,\ k=45.0$;

Subtask 4($10$ 分):$L=1000,\ R=2000,\ k=3.5$;

Subtask 5($10$ 分):$L=2000,\ R=3998,\ k=2.2$;

Subtask 6($10$ 分):$L=2000,\ R=3999,\ k=1.7$,$S$ 中不包含字符 $\text{c}$;

Subtask 7($30$ 分):$L=2000,\ R=4000,\ k=1.7$。

提示:你可以通过 $R$ 判定子任务编号。

21 人解决,78 人已尝试。

24 份提交通过,共有 920 份提交。

7.3 EMB 奖励。

创建: 6 月,1 周前.

修改: 5 月,3 周前.

最后提交: 5 月前.

来源: N/A

题目标签