这是一个交互问题。
伊戈尔想要找到打开奥尔哈心脏的钥匙。问题是,它位于二叉树的根部。
存在一棵高度为 $$$h$$$ 的完美二叉树,由 $$$n = 2^{h} - 1$$$ 个节点组成。这些节点已被分配从 $$$1$$$ 到 $$$n$$$ 的不同标签。然而,Igor只知道$$$h$$$,并不知道哪个标签对应哪个节点。
为了找到 Olha 心脏的钥匙,他需要通过最多 $$$n+420$$$ 次进行以下类型的查询来找到分配给根的标签:
- 选择三个不同的标签 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1 \leq u,v,w \leq n$$$)。
- 作为回应,Olha(评分者)将告诉他标记为 $$$u$$$ 和 $$$v$$$ 的节点的最低公共祖先的标签,如果树根于标记为 $$$w$$$ 的节点。
Help Igor to find the root!
注意:分级器不具有自适应性:标签在进行任何查询之前是固定的。
输入
第一行也是唯一一行包含一个整数 $$$h$$$ ($$$3 \le h \le 18$$$) — 树的高度。
互动
您通过阅读 $$$h$$$ 开始交互。
要查询标签 $$$u、v、w$$$,请在单独的行中输出“? u v w”。
查询中的数字必须满足 $$$1 \le u, v, w \le n$$$。此外,$$$u \ne v$$$、$$$u \ne w$$$ 和 $$$v \ne w$$$。
作为响应,如果树的根位于 $$$w$$$,您将收到 $$$1 \le x \le n$$$,即 $$$u$$$ 和 $$$v$$$ 的最低共同祖先的标签。
如果您的查询无效或您提出的查询超过 $$$n+420$$$ 查询,程序将打印 $$$-1$$$ 并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。
当确定分配给根的标签时,输出“!r”,其中$$$r$$$是根的标签。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
要破解,请使用以下格式。
第一行应包含一个整数 $$$h$$$ (二叉树的高度)。
在下一行,输出大小为 $$$n = 2^h - 1$$$ 的排列 $$$p$$$。这表示一棵二叉树,其中根标记为 $$$p_1$$$,并且对于 $$$1 < i \le n$$$,$$$p_i$$$ 的父级是 $$$p_{ \lfloor{\frac{i}{2}}\rfloor }$$$。
示例
输入 #1
3 2 7 4
输出 #1
? 7 3 5 ? 1 6 4 ? 1 5 4 ! 4
注意
示例中树对应的标签为 [$$$4$$$,$$$7$$$,$$$2$$$,$$$6$$$,$$$1$$$,$$$5$$$,$$$3$$$],表示根标记为 $$$4$$$,对于 $$$1 < i \le n$$$,其父节点$$$p_i$$$ 是 $$$p_{ \lfloor{\frac{i}{2}}\rfloor }$$$。