/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 を根とする部分木の各頂点に書かれた整数の総和の差の絶対値は 1 である．
この問題の制約下で条件を満たす整数の書き込み方が必ず存在することが証明できます．
制約
- 2\leq N\leq 18
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N
出力
頂点 i に書き込む整数を P_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 を根とする部分木の各頂点に書かれた整数の総和は 14，頂点 3 を根とする部分木の各頂点に書かれた整数の総和は 13 であり，|14-13|=1 である．
- i=2：頂点 4 を根とする部分木の各頂点に書かれた整数の総和は 3，頂点 5 を根とする部分木の各頂点に書かれた整数の総和は 4 であり，|3-4|=1 である．
- i=3：頂点 6 を根とする部分木の各頂点に書かれた整数の総和は 5，頂点 7 を根とする部分木の各頂点に書かれた整数の総和は 6 であり，|5-6|=1 である．
Score : 800 points
Problem Statement
You are given a positive integer N.
There is a complete binary tree with 2^N-1 vertices. The vertices are numbered 1 through 2^N-1.
Vertex 1 is the root, and for each i\ (1\leq i\lt 2^{N-1}), vertex i has vertices 2i and 2i+1 as its children.
Find one way to write an integer between 1 and 2^N-1, inclusive, on the vertices (where all 2^N-1 written integers are distinct) such that the following condition is satisfied.
- For each i\ (1\leq i\lt 2^{N-1}), 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 is 1.
It can be proved that there always exists a way to write the integers satisfying the condition under the constraints of this problem.
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. Output:
P_1 P_2 \ldots P_{2^N-1}
(P_1,P_2,\ldots,P_{2^N-1}) must be a permutation of (1,2,\ldots,2^N-1).
If there are multiple valid ways to write the integers, any of them will be accepted.
Sample Input 1
3
Sample Output 1
1 7 2 3 4 5 6
We can verify that this assignment satisfies the condition, as follows.
- i=1: The sum of the integers written on the vertices of the subtree rooted at vertex 2 is 14, the sum of the integers written on the vertices of the subtree rooted at vertex 3 is 13, and |14-13|=1.
- i=2: The sum of the integers written on the vertices of the subtree rooted at vertex 4 is 3, the sum of the integers written on the vertices of the subtree rooted at vertex 5 is 4, and |3-4|=1.
- i=3: The sum of the integers written on the vertices of the subtree rooted at vertex 6 is 5, the sum of the integers written on the vertices of the subtree rooted at vertex 7 is 6, and |5-6|=1.