← 返回题目列表

Codeforces · 1438/F

F. 奥尔哈和伊戈尔

中文机器翻译题面 查看原题

这是一个交互问题。

伊戈尔想要找到打开奥尔哈心脏的钥匙。问题是,它位于二叉树的根部。

存在一棵高度为 $$$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 }$$$。