← 返回题目列表

Codeforces · 1061/F

F. 失去根

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

如果该图是连通且没有环的,则该图称为树。假设树的根位于某个顶点。如果每个顶点要么是叶子(没有子节点),要么恰好有 $$$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 如下所示: