← 返回题目列表

Codeforces · 2206/A

A. 比较后缀

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

的 判断程序 拥有一个长度为 $$$n$$$ 的隐藏字符串 $$$S$$$,仅由小写拉丁字母组成 (a–z)。您无法访问该字符串。一开始,只给你长度$$$n$$$。

你的任务是使用有限数量的确定所有 $$$n$$$ 后缀的顺序 查询.

对于整数 $$$k$$$ ($$$1 \le k \le n$$$),让 $$$S(k)$$$ 表示从第 $$$k$$$ 个字符开始的 $$$S$$$ 的后缀。特别是,$$$S(1)=S$$$。

在单个查询中,您指定两个不同的整数 $$$i$$$ 和 $$$j$$$。判断程序按字典顺序比较 $$$S(i)$$$ 和 $$$S(j)$$$ 并返回 $$$S(i) \lt S(j)$$$ 或 $$$S(i) \gt S(j)$$$ 给您。请注意,$$$i\not= j$$$ 永远不会出现联系,因为所有后缀都是不同的。

找到 $$$(1,2,\ldots,n)$$$ 的排列 $$$(p_1,p_2,\ldots,p_n)$$$,使得 $$$S(p_1) \lt S(p_2) \lt \cdots \lt S(p_n)$$$。

互动

输入的第一行包含整数 $$$n$$$ ($$$2 \le n \le 1000$$$)。

要发出查询,您的程序应编写一行“查询 $$$i$$$ $$$j$$$" ($$$1 \le i \le n; 1 \le j \le n; i \not= j$$$)。之后,输入行包含 第一 or 第二 变得可用。一行包含 第一 表示 $$$S(i) \lt S(j)$$$,而包含的行 第二 表示 $$$S(i) \gt S(j)$$$。

一旦确定了后缀的顺序,您的程序应该编写一行“答案 $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$"。之后,交互停止,您的程序应该终止,没有额外的输出。

您的程序最多可以发出 $$$6260$$$ 查询。如果您的程序发出超过 $$$6260$$$ 查询,则会被判定为“错误答案”。

保证隐藏字符串 $$$S$$$ 仅由小写字母组成 (a–z).

互动评审注意事项:

  • 评估是非对抗性的,这意味着字符串 $$$S$$$ 是提前选择的,而不是响应您的查询。
  • 写入后不要忘记刷新输出缓冲区。
  • 为您提供了用于本地测试的命令行工具,以及与示例交互相对应的输入文件。您可以下载这些文件。该工具顶部有注释来解释其用途。

示例

输入
复制

4

first

second

first

输出
复制

query 2 1

query 2 4

query 1 3

answer 4 2 1 3

注意

示例交互#1 的说明

在此示例中,假定 $$$S=\texttt{icpc}$$$。四个后缀的顺序为 $$$S(4) \lt S(2) \lt S(1) \lt S(3)$$$,因为 $$$\texttt{c} \lt \texttt{cpc} \lt \texttt{icpc} \lt \texttt{pc}$$$。

在第一个和第三个查询中, 返回 第一 因为 $$$S(2) \lt S(1)$$$ 和 $$$S(1) \lt S(3)$$$。在第二个查询中, 返回 第二 因为 $$$S(2) \gt S(4)$$$。通过这些响应,您可以确定顺序。