小猴子下落
時間限制：3000 ms | 內存限制：65535 KB
難度：3
描述
有一顆二叉樹，最大深度為D,且所有葉子的深度都相同。所有結點從左到右從上到下的編號為1,2,3，·····，2的D次方減1。在結點1處放一個小猴子，它會往下跑。每個內結點上都有一個開關，初始全部關閉，當每次有小猴子跑到一個開關上時，它的狀態都會改變，當到達一個內結點時，如果開關關閉，小猴子往左走，否則往右走，直到走到葉子結點。
一些小猴子從結點1處開始往下跑，最后一個小猴兒會跑到哪里呢？
輸入
輸入二叉樹葉子的深度D,和小猴子數目I，假設I不超過整棵樹的葉子個數，D<=20.最終以 0 0 結尾
輸出
輸出第I個小猴子所在的葉子編號。
樣例輸入
4 2
3 4
0 0
樣例輸出
12
7
完全二叉樹，右邊為2*k，左邊為2*k+1。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int text[1<<20];
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0)break;int a=(1<<n)-1;int k;memset(text,0,sizeof(text));for(int i=0;i<m;i++){k=1;while(1){text[k]=!text[k];if(text[k]==0)k=k*2+1;elsek=k*2;if(k>a)break;}}printf("%d\n",k/2);}return 0;
}
