Tournament Countdown

题意翻译

### 题目描述 这是一道交互题。 有一场由 $2^n$ 位选手组成的锦标赛。 这个锦标赛的规则如下：第 $1$ 位选手与第 $2$ 位选手竞争，第 $3$ 位选手与第 $4$ 位选手竞争……以此类推，比赛结束时会只剩下一位参赛选手，这位参赛选手就是胜利者。 你不知道比赛的结果，但你想通过询问评审团来得知最后谁赢了。 每次询问评审团，你需要给定两个正整数 $a$ 和 $b$，$a$ 和 $b$ 分别代指两位选手的编号。 若 $a$ 选手 比 $b$ 选手 赢的回合更多，评委团将报出数字 $1$；如果 $b$ 选手 比 $a$ 选手 赢的回合更多，评审团将报出数字 $2$；如果这两位选手赢的回合一样多，评审团会报出数字 $0$。 你要做的是在不超过 $\lceil \frac{1}{3} \cdot 2^{n+1} \rceil$ 的次数内找到最后胜利的选手。此处 $\lceil x \rceil$ 表示四舍五入 $x$ 到最近的整数。 这场锦标赛已经过去很久了。所以保证有唯一解。 ### 输入格式 输入第一行是一个正整数 $t\ (1\leq t\leq 2^{14})$，表示测试组数。 第二行是一个正整数 $n\ (1\leq n\leq 17)$，作用如题目所述。 接下来若干行都是一个正整数，表示询问的结果。 保证所有测试用例之和不超过 $2^{17}$。 ### 输出格式 读取到 $n$ 后即开始询问。 要进行查询，请输出 " $?\ a\ b$ " $ (1\leq a, b\leq 2^n)$ 不包括引号。 若读入到了 $-1$ 或非有效值，这意味着程序在之前或现在**给出了无效的询问，或者是给出了错误的答案，或者是超出了查询的限制**。此时应停止程序。 若已经确定答案，且要给出答案，请输出 " $!\ x$ " $(1\leq x\leq 2^n)$ 不包括引号，且 $x$ 表示当前判断的最后的赢家。给出答案的次数无限制，即，给出答案不会计入到已询问的次数中。 注意，在每次**回答完成当前数据组或回答完成全部数据组**，程序都应该立即跳出，并刷新缓存区（~~不然呢？ILE大礼包警告~~），你可以： - 在 `C++`，使用 `fflush(stdout)` 或 `cout.flush()` 或 `cout<<endl`； - 在 `Java` 使用 `System.out.flush()`； - 在 `Pascal` 使用 `flush(output)`； - 在 `Python` 使用 `stdout.flush()`； - 其他语言自行查阅对应文档。 要调试你的程序，可以参考以下说明： 1. 第一行输入一个整数 $t$ $(1 \leq t \leq 2^{14})$，表示测试组数； 2. 对于每组测试数据： 1. 第一行输入一个整数 $n$ $(1 \leq n \leq 17)$； 2. 接下来若干行，对于程序提出的询问，依照情况作出回答； 3. 应该保证有唯一解，且给出的数据没有错误。

题目描述

This is an interactive problem. There was a tournament consisting of $ 2^n $ contestants. The $ 1 $ -st contestant competed with the $ 2 $ -nd, the $ 3 $ -rd competed with the $ 4 $ -th, and so on. After that, the winner of the first match competed with the winner of second match, etc. The tournament ended when there was only one contestant left, who was declared the winner of the tournament. Such a tournament scheme is known as the single-elimination tournament. You don't know the results, but you want to find the winner of the tournament. In one query, you select two integers $ a $ and $ b $ , which are the indices of two contestants. The jury will return $ 1 $ if $ a $ won more matches than $ b $ , $ 2 $ if $ b $ won more matches than $ a $ , or $ 0 $ if their number of wins was equal. Find the winner in no more than $ \left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil $ queries. Here $ \lceil x \rceil $ denotes the value of $ x $ rounded up to the nearest integer. Note that the tournament is long over, meaning that the results are fixed and do not depend on your queries.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2^{14} $ ) — the number of test cases. The only line of input contains a single integer $ n $ ( $ 1 \leq n \leq 17 $ ). It is guaranteed that the sum of $ 2^n $ over all test cases does not exceed $ 2^{17} $ .

输出格式

The interaction for each test case begins by reading the integer $ n $ . To make a query, output "? a b" ( $ 1 \leq a, b \leq 2^n $ ) without quotes. Afterwards, you should read one single integer — the answer for your query. You can make at most $ \left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil $ such queries in each test case. If you receive the integer $ -1 $ instead of an answer or a valid value of $ n $ , it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream. When you are ready to give the final answer, output "! x" ( $ 1 \leq x \leq 2^n $ ) without quotes — the winner of the tournament. Giving this answer does not count towards the limit of queries. After solving a test case, your program should move to the next one immediately. After solving all test cases, your program should be terminated immediately. After printing a query or the answer do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks To hack, use the following format. The first line contains an integer $ t $ ( $ 1 \leq t \leq 2^{14} $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 17 $ ). The second line of each test case contains $ 2^n $ numbers on a line — the number of wins of each participant. There should be a sequence of matches that is consistent with the number of wins. The sum of $ 2^n $ should not exceed $ 2^{17} $ .

输入输出样例

输入样例 #1

1
3

2

0

2

输出样例 #1

? 1 4

? 1 6

? 5 7

! 7

说明

The tournament in the first test case is shown below. The number of wins is $ [1,0,0,2,0,1,3,0] $ . In this example, the winner is the $ 7 $ -th contestant.

**题目大意：**
这是一道交互题。有一个由 $2^n$ 位选手组成的单淘汰锦标赛，你需要通过询问评委团来找出最后的胜者。每次询问需要给出两个选手的编号 $a$ 和 $b$，评委团会告诉你谁赢得的场次更多，或者两人赢得的场次是否相同。在不超过 $\lceil \frac{1}{3} \cdot 2^{n+1} \rceil$ 次询问内确定胜者。保证每个测试案例都有唯一解。

**输入格式：**
第一行是一个正整数 $t$（$1 \leq t \leq 2^{14}$），表示测试案例数。
接下来每一组测试数据包含一个整数 $n$（$1 \leq n \leq 17$）。

**输出格式：**
对于每个测试案例，输出若干行，每行格式为 "? a b" 表示一次询问，其中 $a$ 和 $b$ 是两位选手的编号。
当确定胜者后，输出一行 "! x" 表示最后的胜者是编号为 $x$ 的选手。
在输出每次询问或答案后，需要刷新输出缓冲区以避免超时。

**样例输入输出：**
输入：
```
1
3
```
输出：
```
? 1 4
? 1 6
? 5 7
! 7
```
在这个样例中，编号为 7 的选手是最后的胜者。**题目大意：** 这是一道交互题。有一个由 $2^n$ 位选手组成的单淘汰锦标赛，你需要通过询问评委团来找出最后的胜者。每次询问需要给出两个选手的编号 $a$ 和 $b$，评委团会告诉你谁赢得的场次更多，或者两人赢得的场次是否相同。在不超过 $\lceil \frac{1}{3} \cdot 2^{n+1} \rceil$ 次询问内确定胜者。保证每个测试案例都有唯一解。 **输入格式：** 第一行是一个正整数 $t$（$1 \leq t \leq 2^{14}$），表示测试案例数。 接下来每一组测试数据包含一个整数 $n$（$1 \leq n \leq 17$）。 **输出格式：** 对于每个测试案例，输出若干行，每行格式为 "? a b" 表示一次询问，其中 $a$ 和 $b$ 是两位选手的编号。 当确定胜者后，输出一行 "! x" 表示最后的胜者是编号为 $x$ 的选手。 在输出每次询问或答案后，需要刷新输出缓冲区以避免超时。 **样例输入输出：** 输入： ``` 1 3 ``` 输出： ``` ? 1 4 ? 1 6 ? 5 7 ! 7 ``` 在这个样例中，编号为 7 的选手是最后的胜者。