Xmas Contest 2016 夜の部

B - Binary Tree


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 100

問題文

うさぎは完全二分木を持っている.この完全二分木の深さは 11 であり,つまり頂点数は 4095 である.

うさぎはこの完全二分木を以下のように二次元平面に埋め込もうとしている.

  • 各頂点をそれぞれ異なる格子点に埋め込む.
  • 辺は頂点が埋め込まれた格子点どうしを結ぶ線分となる.
  • 辺どうしは端点以外で交差しない.
  • 辺上には端点以外の格子点を含まない.

入力

この問題では入力は与えられない.

出力

頂点の埋め込む格子点の座標を,通りがけ順in-orderで出力せよ.ただし,座標を表す整数は 0 以上 10^9 以下の整数でなければならない.

採点

  • 想定解の座標の最大値を x,提出された解答の座標の最大値を y としたとき,\sqrt{10000*x/y} の小数点以下を切り捨てた値が得点となる.
  • ただし,問題文中の条件を満たしていない場合は 0 点となる.

出力例

以下は,深さが 11 ではなく 2 であった場合の出力例である.

1 2
0 1
0 2
0 0
2 2
3 2
1 1

この出力例の場合,完全二分木は下図のように埋め込まれており,座標の最大値は 3 となる.


Submit提出する