/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
正整数 N が与えられます．
頂点数が 2^N - 1 の完全二分木があります．頂点には 1 から 2^N - 1 までの番号が付いています．
頂点 1 が根であり，頂点 i (1 \leq i < 2^{N - 1}) について，頂点 i は頂点 2i と頂点 2i + 1 を子として持ちます．
以下の条件を満たすように各頂点に 1 以上 2^N - 1 以下の整数を書き込む (ただし，書き込む 2^N - 1 個の整数は相異なるようにする) 方法のうち，頂点 1 に書き込まれる整数を最小化するものを一つ求めてください．
- 頂点 i (1 \leq i < 2^{N - 1}) について，頂点 i に書き込まれた整数は，頂点 2i を根とする部分木の各頂点に書かれた整数の総和と，頂点 2i+1 を根とする部分木の各頂点に書かれた整数の総和の差の絶対値である．
この問題の制約下で条件を満たす整数の書き込み方が必ず存在することが証明できます．
制約
- 2 \leq N \leq 18
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
出力
頂点 i (1 \leq i \leq 2^N - 1) に書き込む整数を P_i として以下の形式で出力せよ．
P_1 P_2 \cdots P_{2^N - 1}
(P_1, P_2, \cdots, P_{2^N - 1}) は (1, 2, \cdots, 2^N - 1) の順列である必要がある．条件を満たす書き込む方法のうち，頂点 1 に書き込まれる整数を最小化するものが複数存在する場合には，そのどれを出力しても正解と見なされる．
入力例 1
2
出力例 1
1 2 3
この書き込み方が条件を満たすことは，以下のようにして確かめられます．また明らかに頂点 1 に書き込まれた整数は最小化されています．
- i = 1: 頂点 2 を根とする部分木の各頂点に書かれた整数の総和は 2，頂点 3 を根とする部分木の各頂点に書かれた整数の総和は 3 であり，∣2 − 3∣ = 1 である．
頂点 1, 2, 3 にそれぞれ 2, 3, 1 を書く方法は，条件を満たしていますが頂点 1 に書き込まれた整数は最小値ではないので不正解と判定されます．
Score : 800 points
Problem Statement
You are given a positive integer N.
There is a perfect binary tree with 2^N - 1 vertices. The vertices are numbered from 1 to 2^N - 1.
Vertex 1 is the root, and for each vertex i (1 \leq i < 2^{N - 1}), vertex i has vertex 2i and vertex 2i + 1 as its children.
Among the ways to write an integer between 1 and 2^N - 1, inclusive, on each vertex (where the 2^N - 1 written integers must be pairwise distinct) such that the following condition is satisfied, find one that minimizes the integer written on vertex 1.
- For each vertex i (1 \leq i < 2^{N - 1}), the integer written on vertex i is the absolute difference between the sum of the integers written on the vertices of the subtree rooted at vertex 2i and the sum of the integers written on the vertices of the subtree rooted at vertex 2i+1.
It can be proved that, under the constraints of this problem, a way of writing integers satisfying the condition always exists.
Constraints
- 2 \leq N \leq 18
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Let P_i be the integer written on vertex i (1 \leq i \leq 2^N - 1), and output in the following format:
P_1 P_2 \cdots P_{2^N - 1}
(P_1, P_2, \cdots, P_{2^N - 1}) must be a permutation of (1, 2, \cdots, 2^N - 1). If there are multiple ways of writing satisfying the condition that minimize the integer written on vertex 1, any of them will be considered correct.
Sample Input 1
2
Sample Output 1
1 2 3
It can be verified as follows that this way of writing satisfies the condition. Also, the integer written on vertex 1 is clearly minimized.
- i = 1: The sum of the integers written on the vertices of the subtree rooted at vertex 2 is 2, the sum of the integers written on the vertices of the subtree rooted at vertex 3 is 3, and ∣2 − 3∣ = 1.
The way of writing 2, 3, 1 on vertices 1, 2, 3, respectively, satisfies the condition, but the integer written on vertex 1 is not the minimum, so it will be judged as incorrect.