No.566 だいたい完全二分木

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 104
作問者 : 紙ぺーぱー紙ぺーぱー / テスター : ixmelixmel
5 ProblemId : 1159 / 出題時の順位表

問題文

だいたい完全二分木は $2^{K}-1$個の頂点からなる二分木であって、木の高さが$K$ 以上 $3K$ 以下であるような二分木である。高さとは各辺の長さを $1$ としたときに根から最も遠い頂点までの距離のことを指す。
今日もあなたはだいたい完全二分木を $1$ つ構築することにした。

構築の手順は $\{1, 2, 3 , \ldots, 2^{K} - 1 \}$ を並び替えた数列 $P_1, P_2, \ldots, P_{2^K - 1} $ によって定められる。
具体的な手順としては $0$ 個の要素からなる二分探索木 $T$ に $P_1, P_2, \ldots , P_{2^{K}- 1}$ をこの順序で挿入する。
二分探索木 $G$ に値 $v$ を挿入するときのルールは以下のように再帰的に定義される。

  • $G$ に頂点が存在しないならば $v$ を $G$ の根にする。
  • $G$ に頂点が存在するならば $v$ と根の値を比較し、 $v$ の方が小さいならば左の部分木に、 そうでないならば右の部分木に挿入する。
$K=2$ において、例えば、$( 1,3,2 ), (2,1,3)$ から、 以下の図のような二分木がそれぞれ最終的に得られる。
$( 1,3,2 )$ から得られる二分木は高さが $2$ なのでだいたい完全二分木だが、 $(2,1,3 )$ から得られる二分木は高さが $1$ なのでだいたい完全二分木ではない。

この手順により得られる二分探索木 $T$ がだいたい完全二分木になるような数列をどれか $1$ つ求めよ。
解が $1$ つ以上存在することが保証される。

入力

$K$

整数 $K(2 \leq K \leq 12)$ が $1$ 行で与えられる。

出力

条件を満たすような二分木の構築手順を定める数列 $P$ を空白区切りで $1$ 行に出力せよ。
条件を満たすものであればどれでもよい。

サンプル

サンプル1
入力
2
出力
1 3 2

問題文中で示した通りである。
$ (1, 2, 3 ), (1,3,2 ), ( 3,1,2 ), ( 3,2,1 )$ の $4$ つにより構築される二分木が高さ $2$ の条件を満たす二分木となる。
$ ( 2,3,1 ), ( 2,1,3 )$ により構築される二分木は高さが $1$ のため、条件を満たさない。

サンプル2
入力
3
出力
5 3 2 4 1 6 7

以下のような二分木が得られる。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。