分数: 800 点
问题陈述
给你一个正整数 N.
有一个完全二叉树 2^N-1 顶点。顶点已编号 1 通过 2^N-1.
顶点 1 是根,对于每个 i\ (1\leq i\lt 2^{N-1}),顶点 i 有顶点 2i 和 2i+1 作为其子项。
找到一种在之间写入整数的方法 1 和 2^N-1,包含在内,在顶点上(其中所有 2^N-1 所写的整数是不同的),从而满足以下条件。
- 对于每个 i\ (1\leq i\lt 2^{N-1}),以顶点为根的子树的顶点上写入的整数之和之间的绝对差 2i 以及写在以顶点为根的子树的顶点上的整数之和 2i+1 is 1.
可以证明,在该问题的约束下,总存在一种写出满足条件的整数的方法。
约束
- 2\leq N\leq 18
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
输出
让 P_i 是写在顶点上的整数 i。输出:
P_1 P_2 \ldots P_{2^N-1}
(P_1,P_2,\ldots,P_{2^N-1}) 必须是以下排列 (1,2,\ldots,2^N-1).
如果有多种有效的整数写入方式,则任何一种都将被接受。
示例输入 1
3
示例输出 1
1 7 2 3 4 5 6
我们可以验证此分配是否满足条件,如下所示。
- i=1:写在以顶点为根的子树的顶点上的整数之和 2 is 14,写在以顶点为根的子树的顶点上的整数之和 3 is 13,和 |14-13|=1.
- i=2:写在以顶点为根的子树的顶点上的整数之和 4 is 3,写在以顶点为根的子树的顶点上的整数之和 5 is 4,和 |3-4|=1.
- i=3:写在以顶点为根的子树的顶点上的整数之和 6 is 5,写在以顶点为根的子树的顶点上的整数之和 7 is 6,和 |5-6|=1.