← 返回题目列表

Codeforces · 2087/D

D. 大写还是小写?

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

这是一个交互问题。

在某个数据库中,有$$$n$$$个句柄以编号列表的形式存储。您对某个特定句柄 $$$h$$$ 感兴趣,或者更准确地说,对其在此列表中的位置感兴趣。

你可以向数据库询问列表中的位置$$$i$$$,它将返回第$$$i$$$位置的句柄。

所有句柄都是非空字符串,最多包含 $$$20$$$ 小写拉丁字母, 除了第一个 可以是小写或大写拉丁字母。

您知道所有句柄都按字典顺序排序,但问题是不知道大写字母是否被认为小于小写字母。换句话说,您不知道是否所有以大写字母开头的句柄首先出现,然后是以小写字母开头的句柄,反之亦然,即所有以小写字母开头的句柄首先出现,然后是以大写字母开头的句柄。

词典顺序是标准字符串比较的顺序,正式定义如下:

  • 如果字符串 $$$s$$$ 和 $$$t$$$ 在某些位置不同,其中最早的是位置 $$$i$$$,则字符串 $$$s$$$ 按字典顺序排在字符串 $$$t$$$ 之前当且仅当 $$$s_i \lt t_i$$$ (例如,对于字符串 猫 和 当前,第一个不同字符的位置是$$$2$$$,并且字符 a 小于字符 u,所以 猫 按字典顺序小于 当前);
  • 如果字符串 $$$s$$$ 和 $$$t$$$ 没有包含不同字符的位置,则较短的位置在前。例如,字符串 猫 位于字符串之前 猫.

由于对数据库的访问受到限制,您最多只能对数据库进行 $$$10$$$ 查询。确定您感兴趣的句柄的位置,知道它肯定在列表中。

输入

第一行包含数字 $$$n$$$ 和字符串 $$$h$$$ ($$$1 \le n \le 500$$$) - 列表中的句柄总数以及您正在搜索的句柄。

保证所有句柄都是不超过 $$$20$$$ 个字符的非空字符串,仅由小写拉丁字母组成,第一个字母可能是大写字母。

还保证所有句柄都是排序的、唯一的,并且给定的句柄位于列表中。

互动

要提出问题,请按以下格式输出字符串(不带引号):

  • "?我" ($$$1 \le i \le n$$$)

陪审团将返回一个字符串 $$$s$$$ — 列表中第 $$$i$$$ 位置的句柄。

当您准备好打印答案时,按以下格式输出单个字符串(不带引号):

  • "!我" ($$$1 \le i \le n$$$)
并终止程序。打印答案 不 计为查询。

交互器不是自适应的,这意味着每个测试中的句柄列表都是预先固定的。

如果您的程序询问超过 $$$10$$$ 查询(不包括打印答案)或违反查询格式,评审团将使用字符串“-1“。在这种情况下,您的程序应立即终止以接收以下判决: 错误答案。否则,您可能会收到任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出换行符并刷新输出。否则,您可能会收到以下判决: 超出空闲限制。为此,请使用 System.out.flush().

示例

输入
复制

4 adedalic

Bleddest

Neon

adedalic

awoo

输出
复制

? 1

? 2

? 3

? 4

! 3

输入
复制

6 tourist

jiangly

tourist

Radewoosh

输出
复制

? 1

? 3

? 6

! 3

注意

请注意,示例中添加空格只是为了提高可读性。检查解决方案时,交互器不会输出任何空行。