题意
这是一道交互题。
有一场 $2^n$ 个人参加的淘汰赛，结果已定，你最多使用 $ \left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil $ 次询问，求出淘汰赛的冠军编号。每次询问的格式为 ? a b，表示询问编号为 $a$ 的人和编号为 $b$ 的人哪个赢的次数多，询问的答案为 $0$ 或 $1$ 或 $2$ 表示 $a$ 赢的场数等于、大于或小于 $b$。最后输出 ! a，表示淘汰赛的冠军编号。
$1 \leq n\leq 17$。
思路
先考虑 $n=1$ 的情况，显然直接询问 ? 1 2 即可求出答案。
考虑 $n=2$ 的情况，
如图，$1$ 和 $2$ 中一定有一个在第一轮就被淘汰了，$3$ 和 $4$ 也是，第一轮之后剩下的两个一定有一个是冠军，赢的场数一定不同且比被淘汰的人多。被淘汰的人赢的场数是一样的。
我们可以询问 ? 1 3，如果得到答案是 $0$，就得出 $1$ 和 $3$ 都被淘汰了，冠军只可能是 $2$ 或 $4$，一次询问得出答案；
如果答案是 $1$ 或 $2$，那么赢的场数较少的那一个人一定不可能是冠军，和赢的场数较多的人在第一轮比赛的人也一定不可能是冠军。因此就只剩两个人有可能是冠军了，一次询问得出答案。
综上，$n=2$ 时，可以通过两次询问确定答案。
考虑 $n > 2$ 的情况。
当 $2 \mid n$ 时，画出来的赛况图（像样例解释那样的）一定可以分为若干个 $n=2$ 的情况。考虑对赛况图进行搜索，用每个点代表这一层代表的轮中这一个位置人的编号，则根节点的值就是答案，如样例中的图：
对于每个从上往下数奇数层（除最后一层外）上的点，一定可以从最后一层开始用 $2$ 次询问求出这个点的答案，再用这个答案往上求答案。此时总共有 $2^n (\frac {1}{2}+\frac{1}{8}+\frac{1}{32}+\dots+\frac{1}{2^{n-1}}) = 2^{n-1}(1+\frac{1}{4}+\frac{1}{16}+\dots+\frac{1}{2^{n-2}})=2^{n-1}\times \frac{4}{3}(1-\frac{1}{2^n})=\frac{1}{3}\times 2^{n+1}(1-\frac{1}{2^n})$ 次询问，满足题意；
当 $2 \nmid n$ 时，画出来的赛况图一定可以分为若干个 $n=2$ 的情况和一个 $n=1$ 的情况，可以类比 $2 \mid n$ 的情况。此时总共有 $2 ^n (\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\dots+\frac{1}{2^{n-2}})+1 = 2^n(\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\dots+\frac{1}{2^{n-2}}+\frac{1}{2^n}) = 2^{n+1}\times \frac{4}{3}(1 - \frac{1}{2^{n+1}})$ 次询问，满足题意。
代码
1 |
|