下落的小球
时间限制: 1 s
内存限制: 128 MB
提交：15
正确：10
分值：100
题目描述
有如下图的一颗二叉树，最大深度为d，且所有叶子的深度都相同。所有结点从上到下从左到右的编号为1、2、3、4……、2d-1。在节点1处放一小球，它会往下落。每个结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。如果一些小球从结点1处依次开始下落，问最后一个小球会落向哪个叶子结点？
输入
输入二叉树的深度d和小球个数n，以空格间隔。d<=16，n不超过整棵树的叶子个数。
输出
输出第n个小球最后所在的叶子编号
样例
样例输入:
4 2
样例输出:
12
样例输入:
3 4
样例输出:
7
提示
有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有
(1)如果i>1，则其父节点是floor(i/2) floor( )向下取整的意思
(2)如果2i>n，则结点i无左孩子，否则左孩子为2i
(3)如果2i+1>n，则结点i无右孩子，否则右孩子为2i+1
深度为k的满二叉树，有2^k - 1个结点