← 返回题目列表

Codeforces · 1267/I

I. 有趣的选择

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

这是一个交互问题。

你是国际象棋俱乐部的主教练。俱乐部有$$$2n$$$球员,每个球员都有一定的实力,可以用一个数字来表示,并且所有这些数字都是不同的。球员的实力你不知道。

您需要选择 $$$n$$$ 球员来代表您的俱乐部参加即将举行的锦标赛。当然,您希望选择实力最强的 $$$n$$$ 玩家。

您可以组织玩家之间的比赛来做到这一点。在每场比赛中,你选择两名球员,让他们打一些比赛,然后你就可以知道这两人中哪一个实力更高。您可以等待一场比赛的结果,然后再决定谁将参加下一场比赛。

然而,您不想确切地知道这些 $$$n$$$ 玩家之间的比较,因为这会让锦标赛本身变得不那么有趣。更正式地说,您必须达到这样一种状态:恰好有一种方法可以选择具有最高实力且与您组织的比赛结果一致的 $$$n$$$ 球员,但这些 $$$n$$$ 球员的实力必须至少有两种可能的排序,并且与您组织的比赛结果一致。

互动

您的程序必须在一次运行中处理多个测试用例。首先,它应该读取整数 $$$t$$$ ($$$t \ge 1$$$) — 测试用例的数量。然后,它应该一一处理测试用例。

在每个测试用例中,您的程序应首先读取整数 $$$n$$$ ($$$3 \le n \le 100$$$) — 从 $$$2n$$$ 玩家中选择的玩家数量。所有测试用例的 $$$n$$$ 值的平方和不超过 $$$10\,000$$$。

然后你的程序可以组织比赛零次或多次。要组织一场比赛,您的程序应该打印格式为 ? 的比赛描述。 $$$i$$$ $$$j$$$ - 一个问号,后面跟着两个不同数量的参加比赛的玩家。玩家编号从 1 到 $$$2n$$$(含)。请记住在打印匹配描述后刷新输出。然后您的程序应该读取比赛结果 - 如果比赛描述中的第一个玩家具有更高的强度,则它将是大于字符 (>);如果比赛描述中的第二个玩家具有更高的强度,则它将是小于字符 (<)。

您的程序最多可以组织 $$$4n^2$$$ 比赛。组织完匹配后,它应该打印感叹号(!)并继续下一个测试用例,或者如果这是最后一个测试用例则优雅地退出。请记住在打印感叹号后刷新输出。

必须有一种方法来选择具有最高实力且与您组织的比赛结果一致的 $$$n$$$ 球员,但这些 $$$n$$$ 球员的实力必须至少有两种可能的排序方式,并且与您组织的比赛结果一致。

在您的程序开始组织比赛之前,评审程序会选择一些不同的数字作为所有玩家的优势,并使用它们来回答请求。

示例

输入 #1

2
3

>

<

>

<

>

>

3

<

<

<

>

>

输出 #1

? 1 3

? 4 2

? 4 5

? 6 5

? 3 4

? 5 6

!

? 3 4

? 4 2

? 5 3

? 6 4

? 3 1

!

注意

在该示例中,第一个测试用例中的玩家按实力降序排列。从示例输出中的比赛中,我们可以推断出玩家 1、2 和 3 的强度最高,但我们不知道玩家 1 与玩家 2 相比如何。