一棵深度为D满二叉树层次遍历编号从1到2^D-1，有X个小球一次从1掉落，可以掉落到左子树或者右子树，每一个内部结点都有一个开关，起初开关都是关闭着的，当小球进入结点后，如果开关是关闭，则开关改变成为开，小球落入左子树，相反同理。现在给出D和X求出第X个小求落在的结点编号。
思路:经过一两次模拟后，发现：在根节点时，奇数y个小球总是落在左子树，并且是第(y+1)/2个落入该左子树的。偶数y个小球总是落在右子树，并且是第y/2个落入该右子树。因此小球最后落入的结点的编号只与第X个小球，X的奇偶性有关，所以直接模拟最后一个小球的掉落过程即可得出答案。
#include<cstdio>
using namespace std;int main(){freopen("input.txt","r",stdin);int d,I,t;while(scanf("%d",&t)==1){if(t==-1)break;for(int i=0 ;i<t ;i++){int k = 1;scanf("%d%d",&d,&I);for(int i=0 ;i<d-1 ;i++){if(I%2){k = 2*k; I = (I+1)/2;}//奇数 else{k = 2*k+1; I = I/2;}//偶数 }printf("%d\n",k);}}return 0;
}