这是一个交互问题。
法官有一棵有 n 个叶子的隐藏有根满二叉树。满二叉树是每个节点都有 0 或 2 个子节点的树。具有 0 个子节点的节点称为树的叶子。由于这是一棵满二叉树,因此树中恰好有 2n - 1 个节点。法官树的叶子有从 1 到 n 的标签。您想要重建一棵与法官树同构的树。为此,您可以提出一些问题。
问题包括打印三个不同叶子 a1、a2、a3 的标签。设节点的深度为该节点到树根的最短距离。令 LCA(a, b) 表示具有最大深度的节点,该节点是节点 a 和 b 的共同祖先。
考虑 X = LCA(a1, a2),Y = LCA(a2, a3),Z = LCA(a3, a1)。法官会告诉你X、Y、Z中哪一个的深度最大。注意,由于该树是二叉树,因此该对是唯一确定的;不可能有任何联系。
更具体地说,如果 X(或分别为 Y、Z)最大化深度,则法官将用字符串“X”(或分别为“Y”、“Z”)进行响应。
您最多只能提出 10·n 个问题。
输入
输入的第一行将包含一个整数 n (3 ≤ n ≤ 1 000) - 树中叶子的数量。
互动
要提出问题,请打印出三个不同的整数 a1、a2、a3。这些整数应介于 1 和 n 之间(含 1 和 n)。
法官将回答一个字符,“X”、“Y”、“Z”。
如果字符串是“X”(或分别为“Y”、“Z”),则表示对(a1,a2)(或分别为(a2,a3),(a3,a1))在三对中具有最深的LCA。
一个问题最多只能问10·n次,否则,你会得到错误的答案。
当您准备好回答时,在其自己的行上打印出一个整数“-1”。下一行应包含 2n - 1 个整数。第 i 个整数应该是第 i 个节点的父节点,如果是根节点,则为 -1。不要忘记刷新最终答案。打印答案不算提出问题。
如果出现以下情况,您将得到错误答案判决:
- 您的问题或答案不符合本声明中描述的格式。
- 您提出的问题严格超过 10·n 个。
- 您的问题包含重复的索引。
- 你的最终答案与判断树并不同构。
如果您不打印任何内容或者忘记刷新输出,包括最终答案(有关刷新输出的更多信息,请参阅下面),您将收到“超出空闲限制”信息。
要刷新,您可以使用(在打印整数和行尾之后):
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。
如果您的程序在任何时候读取 -1 作为答案,它应该立即正常退出(例如,通过调用 exit(0))。在这种情况下,您将得到错误答案,这意味着您进行的查询超出了允许的范围,或者进行了无效查询。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。
黑客攻击 要攻击某人,请使用以下格式
这表示一棵树,其中第 i 个节点的父节点是 pi(pi = - 1 或 n < pi ≤ 2n - 1)。如果 pi 等于 -1,则节点 i 是根。该输入必须描述有效的全根二叉树。
当然,参赛者程序将无法看到此输入。
输出
要打印最终答案,请在其自己的行上打印字符串“-1”。然后,下一行应包含 2n - 1 个整数。第 i 个整数应该是第 i 个节点的父节点,如果是根节点,则为 -1。
如果你的输出与判断树同构,你的答案将被判断为正确。特别是叶子的标签不需要从1到n进行标签。这里,同构意味着存在一个排列 π,使得节点 i 是判断树中节点 j 的父节点,当且仅节点 π(i) 是树中节点 π(j) 的父节点。
示例
输入 #1
5 X Z Y Y X
输出 #1
1 4 2 1 2 4 2 4 1 2 3 5 2 4 3 -1 -1 1 1 2 2 3 3 6 6
注意
对于第一个样本,判断者有隐藏树:
这是一种更易读的交互格式:
$$\begin{数组}{|c|c|}
\hline
\text{裁判} & \text{参赛者} \\
\hline
5 & 142 \\
X & 124 \\
Z & 241 \\
Y & 235 \\
Y & 243 \\
X & -1 \\
& -1112233366 \\
\hline
\end{数组}$$