← 返回题目列表

AtCoder · agc044_d

D. 猜密码

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

分数: 1100 点

问题陈述

这是一项交互式任务。

你必须猜测一个秘密密码 S。 密码是一个非空字符串,其长度最多为 L。 密码的字符可以是小写和大写英文字母(a、b、...、z、A、B、...、Z)和数字(0、1、...、9)。

为了猜测秘密密码 S 您可以提问。 查询有效密码 T,此类查询的答案是之间的编辑距离 S 和 T (编辑距离考虑的操作有:删除、插入、替换)。 你最多可以问 Q 查询。

注意:有关编辑距离的定义(包含操作:删除、插入、替换),请参见 这个维基百科页面.

约束

  • L = 128
  • Q = 850
  • 秘密密码 S 在交互开始之前选择。

互动

要提出查询,请在标准输出上打印(末尾带有换行符)

? T

字符串 T 必须是有效的密码。

答案 ans 应以以下形式从标准输入读取:

ans

确定隐藏密码后 S,您应该在标准输出上打印(末尾有换行符)

! S

并终止您的程序。

判断

  • 每次输出后,您必须刷新标准输出。 否则你可能会得到 TLE.
  • 打印(您猜测的)隐藏密码后,必须立即终止程序。否则,法官的行为是不确定的。
  • 如果您确定的密码错误,您将得到 WA.
  • 如果您询问格式错误的查询(例如,因为该字符串不是有效的密码,或者您忘记输入 ?)或者如果你的程序崩溃或者你询问超过 Q 查询,判断的行为未定义(它不一定给出 WA).

样品

在此问题的唯一示例测试用例中,隐藏密码是 Atcod3rIsGreat.

下面是一个交互示例,如果 S=Atcod3rIsGreat.

输入 输出
\texttt{? AtcoderIsBad}
5
\texttt{? AtcoderIsGreat}
1
\texttt{! Atcod3rIsGreat}