COCI 2006/2007, Contest #4

Task JOGURT

A complete binary tree is made of nodes arranged in a hierarchic structure. One of the nodes is the root node, said to be at level 0. The root node has two child nodes, which are at level 1. Each of those has two children at level 2 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 L−1.

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 D, 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^D.

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 1 must differ by 2.

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

Input

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

Output

Output the 2^N−1 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.

Sample Tests

2

3 1 2

3

3 1 7 5 6 2 4

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 22, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I think the judge doesn't work correctly. Please check it!

16:10: [s]I previously said I wouldn't look into it. I think I actually will though; please give me a little bit.[/s]
16:17: [s]I believe you are correct. I'll look into fixing it.[/s]

Thank you for your report. We previously did not have a custom judge for this problem, and the solutions were simply the results generated by the official solution. If you happened to write your output in the exact same way, then you got AC; otherwise, even if you had a correct solution, you got WA.

I wrote a custom judge for this problem, and I've rejudged some submissions. The following users now get AC for their correct solutions:
[list]
[*] duong211199
[*] klime
[*] mahdigh
[*] MuhammadKhattak
[*] suchir
[*] Thomas_Orton
[/list]
In addition, I found the following user to have cheated by copying the official solution verbatim. Accordingly, I've deleted said submission.
[list]
[*] branko_fu
[/list]
For posterity, the following users happened to produce output in the exact same order as the official submission. I briefly reviewed their code and could not determine any obvious signs of cheating.
[list]
[*] gskhirtladze
[*] thomasmikava
[/list]
Either way, their submissions were rejudged for posterity.

Edit: I'm amused that I've received downvotes for this comment.