/ Vijos / 题库 /

三叉树的计算

三叉树的计算

时间限制:1秒  内存限制:256M


【问题描述】

  一个深度为 \(h\)(根结点深度为\(1\))的完全三叉树,按前序遍历的顺序给结点从 \(1\) 开始编号,则第 \(n\) 号结点的父结点是多少号?请你编程计算。

【输入格式】

  包含若干组数据,每组数据为一行两个正整数:\(h\) 和 \(n\)。

【输出格式】

  每组数据输出一行一个整数,表示对应 \(n\) 父亲的编号,若不存在则输出 \(-1\)。

【输入输出样例】

 Input

3 5
2 2
4 7
4 37
2 3
5 100
3 14

 Output

2
1
2
28
1
97
-1

【数据范围】

  \(0≤h≤30,1≤n≤10^{18}\)

【来源】

  Mr.he

信息

ID
2866
难度
9
分类
递推 | 树结构 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
1
上传者