A complete binary tree is made of nodes arranged in a hierarchical structure. One of the nodes is the root node, said to be at level \(1\). The root node has two child nodes, which are at level \(2\). Each of those has two children at level \(3\) etc.

In general, a complete binary tree with \(N\) levels has \(2^N - 1\) nodes, each of which has two child nodes, except those at level \(N\).

A number can be written into each node. Write the numbers \(1\) to \(2^N - 1\) into a complete binary tree with \(N\) levels so that, for each node at level \(i\), the absolute value of the difference of the sum of all numbers in the left subtree and the sum of all numbers in the right subtree is \(2^{i-1}\).

For example, the sum of the left subtree of the root node must differ from the sum of the right subtree by \(1\). The sums of the left and right subtrees of a node at level \(2\) must differ by \(2\).

Each number must be used exactly once. The solution need not be unique.

The first and only line of input contains the integer \(N\) (\(1 \le N \le 15\)), the number of levels in the tree.

Output the \(2^N - 1\) integers separated by spaces on a single line, the binary tree in the preorder traversal. The preorder traversal first outputs the number in the root node, then outputs the left subtree (again in the preorder traversal), then the right subtree.

riseoj 작성

출처 COCI 2006/2007 Contest 4