如果该图是连通且没有环的,则该图称为树。假设树的根位于某个顶点。如果每个顶点要么是叶子(没有子节点),要么恰好有 $$$k$$$ 子节点,则树被称为完美的 $$$k$$$-ary 树。此外,在完美的 $$$k$$$-ary 树中,所有叶子必须具有相同的深度。
例如,下图展示了具有 $$$15$$$ 顶点的完美二叉树:
存在一棵完美的 $$$k$$$ 一叉树,其中包含 $$$n$$$ 节点。这些节点用从 $$$1$$$ 到 $$$n$$$ 的不同整数进行标记,但是您不知道如何标记节点。尽管如此,您还是想找到树根的标签。
您最多可以进行 $$$60 \cdot n$$$ 以下类型的查询:
- "? $$$a$$$ $$$b$$$ $$$c$$$",如果标签为 $$$b$$$ 的节点位于 $$$a$$$ 到 $$$c$$$ 的路径上,则查询返回“Yes”,否则返回“No”。
$$$a$$$ 和 $$$c$$$ 都被认为位于从 $$$a$$$ 到 $$$c$$$ 的路径上。
当你准备好报告树的根时,打印
- "! $$$s$$$",其中 $$$s$$$ 是树根的标签。
只能报告根一次,并且此查询不计入 $$$60 \cdot n$$$ 查询的限制。
互动
标准输入流的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k < n$$$) — 树中的节点数和 $$$k$$$ 的值。
保证 $$$n$$$ 使得该树形成完美的 $$$k$$$ 叉树。
您最多可以提出 $$$60 \cdot n$$$ 查询。要提出查询,请打印一行“? $$$a$$$ $$$b$$$ $$$c$$$”,其中$$$1 \le a, b, c \le n$$$。之后,您应该根据查询的答案阅读包含“是”或“否”的一行。
每个测试的树都是固定的,它不依赖于您的查询。
当您准备好打印答案时,打印一行“! $$$s$$$”形式的行,其中$$$s$$$ 是根顶点的标签,然后终止您的程序。
打印每个查询后,不要忘记打印行尾并刷新输出。否则您可能会超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
如果你的程序将进行超过 $$$60 \cdot n$$$ 查询,但在其他方面遵循交互协议并直接终止,它将得到“错误答案”的判决。
黑客
要破解该解决方案,请使用以下测试格式:
第一行应包含整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k \le 1500$$$) — 树的顶点数和 $$$k$$$ 参数。
当然,$$$n$$$ 的值必须对应于某个深度的有效 $$$k$$$ 元树的大小。
第二行应包含 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 树的标签按自然顺序排列,所有标签必须不同。
让我们将树顶点的以下排序称为自然排序:首先是树的根,然后是从根开始的一条边的深度上的所有顶点,从左到右排序,然后是从根开始的两条边的深度上的所有顶点,从左到右排序,依此类推,直到最大深度。
这样,$$$a_1$$$ 就是破解的答案。
示例
输入 #1
3 2 No Yes
输出 #1
? 1 3 2 ? 1 2 3 ! 2
注意
示例中的树如下:
例如,输入和输出说明了该测试中可能的交互(插入空行只是为了清楚起见)。
与该示例相对应的 hack 如下所示: