← 返回题目列表

Codeforces · 730/B

B. 最小值和最大值

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

这是一个交互问题。您必须在打印每一行后立即使用刷新操作。例如,在 C++ 中,您应该使用函数 fflush(stdout),在 Java 中,您应该使用 System.out.flush(),在 Pascal 中,您应该使用函数 fflush(output),在 Python 中,您应该使用 sys.stdout.flush()。

在这个问题中,您需要找到数组的最大和最小元素。还有什么可以更简单呢?

你可以想象陪审团有一个数组,并且最初你知道唯一的数字 n - 数组的长度。

数组的元素编号为 1 到 n。您可以使用索引 i 和 j 来比较数组的两个元素。该查询有三种可能的响应:“<”(如果 ai 小于 aj)、“=”(如果 ai 等于 aj)和最后“>”(如果 ai 大于 aj)。

众所周知,通过使用不超过 $$f(n) = \left\lceil \frac{3 \cdot n}{2} \right\rceil - 2$$ 比较,总是可以找到数组的最大和最小元素,其中 ⌈ x⌉ 是 x 向上舍入的结果。

编写程序,通过使用不超过 f(n) 次比较来查找长度为 n 的陪审团数组中最小值和最大值的位置。

互动

此问题的每个测试都将包含一个或多个数组。您必须找到每个数组的最小和最大元素的位置。输入的第一行包含整数 T (1 ≤ T ≤ 1000) — 测试中的数组数量。

因此,一开始,你的程序应该读取数字T,然后它应该一一解决T陪审团数组的问题。

然后输入每个数组。首先,您的程序必须读取数字 n (1 ≤ n ≤ 50) — 数组的长度。它将在输入的下一行中提供。

此外,您的程序可以执行比较或报告找到答案。

- 要执行比较,您必须输出以下模式的字符串 «? i j»(i 和 j 必须是从 1 到 n 的整数)— 当前查询中要比较的元素的索引。
- 要报告隐藏数组的最小和最大元素的索引,您的程序必须以 «! 的形式输出一行。 i j»(i 和 j 必须是从 1 到 n 的整数),其中 i 是数组最小元素的索引,j 是数组最大元素的索引。如果问题有多个可能的答案,则可以输出其中任何一个。

有几种可能的比较响应:

- '<' — 如果 ai 小于 aj,
- '=' — 如果 ai 等于 aj,
- '>' — 如果 ai 大于 aj。

对于长度为 n 的数组,您的程序最多可以进行 $$f(n) = \left\lceil \frac{3 \cdot n}{2} \right\rceil - 2$$ 比较。请注意,报告答案(《! i j》)的操作不包含在 f(n) 的值中。

报告答案后,您的程序必须解决下一个数组的问题,否则如果处理完所有 T 数组,程序应该终止。

示例

输入 #1

2
2
>
3
=
=

输出 #1

? 1 2
! 2 1
? 3 1
? 2 1
! 2 3