这是一个交互问题。
有一场由 $$$2^n$$$ 参赛者组成的锦标赛。第$$$1$$$-nd 参赛者与第$$$2$$$-nd 竞争,$$$3$$$-rd 与第$$$4$$$-th 竞争,依此类推。之后,第一场比赛的获胜者与第二场比赛的获胜者进行比赛,以此类推。当只剩下一名参赛者时,比赛结束,并被宣布为比赛的获胜者。这种锦标赛计划被称为单淘汰锦标赛。
您不知道结果,但您想找到锦标赛的获胜者。在一个查询中,您选择两个整数 $$$a$$$ 和 $$$b$$$,它们是两个参赛者的索引。如果 $$$a$$$ 赢得的比赛多于 $$$b$$$,则评审团将返回 $$$1$$$;如果 $$$b$$$ 赢得的比赛多于 $$$a$$$,则评审团将返回 $$$2$$$;如果获胜次数相等,则评审团将返回 $$$0$$$。
在不超过 $$$\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$$$ 查询中找到获胜者。这里 $$$\lceil x \rceil$$$ 表示 $$$x$$$ 的值向上舍入到最接近的整数。
请注意,锦标赛早已结束,这意味着结果是固定的,不取决于您的查询。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2^{14}$$$) — 测试用例的数量。
输入的唯一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 17$$$)。
保证所有测试用例的$$$2^n$$$总和不超过$$$2^{17}$$$。
互动
每个测试用例的交互从读取整数 $$$n$$$ 开始。
要进行查询,请输出不带引号的“? a b” ($$$1 \leq a, b \leq 2^n$$$)。然后,您应该读取一个整数——您的查询的答案。在每个测试用例中,您最多可以进行 $$$\left \lceil \frac{1}{3} \cdot 2^{n + 1} \right \rceil$$$ 这样的查询。
如果您收到整数 $$$-1$$$ 而不是答案或有效值 $$$n$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对之前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
当您准备好给出最终答案时,输出不带引号的“! x” ($$$1 \leq x \leq 2^n$$$) — 锦标赛的获胜者。给出此答案不计入查询限制。解决一个测试用例后,您的程序应该立即转移到下一个测试用例。解决所有测试用例后,您的程序应立即终止。
打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式。
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2^{14}$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 17$$$)。
每个测试用例的第二行包含 $$$2^n$$$ 数字 — 每个参与者的获胜次数。应该有一个与获胜次数一致的比赛顺序。
$$$2^n$$$ 的总和不应超过 $$$2^{17}$$$。
示例
输入 #1
1 3 2 0 2
输出 #1
? 1 4 ? 1 6 ? 5 7 ! 7
注意
第一个测试用例中的锦标赛如下所示。获胜次数为$$$[1,0,0,2,0,1,3,0]$$$。
在此示例中,获胜者是第 $$$7$$$ 名参赛者。