B - Binary Tree Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 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 となる．