这是一个交互问题。您必须在打印每一行后立即使用刷新操作。例如,在 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