题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=63

解题思路：

很久前做过这道题，是用的模拟法做的。因为这道题数目的测试数据比较少，所以暴力就过了。

但是如果测试数据很大时，超时是明显的。因为D<=20，所以需要遍历的为2的19次方乘以19，如果有1000组测试数据，就肯定挂了。

今天看到了一种优化，非常巧妙。

因为每个小猴子都是从根节点向下，它必然有两种选择：左、右。而且有规律，它前面的两个猴子一定是左，右。所以在每个节点进入根节点时，我们只需要判断这个点的奇偶性就知道它的方向了。然后它进入根节点的下一层，依然有两种选择，同样的判断，但是数据规模减少一半（每进入1层，舍弃另一个子树，必然减少一半，因为左右的个数相同或者相差1），这样，我们只需要判断这个猴子是第几个进入该层，然后判断奇偶即可。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

int main()
{
	int d, I;
	while(scanf("%d %d", &d, &I) && (d + I))
	{
		int k = 1;
		for(int i = 0; i < d - 1; ++i) //倒数第二层
			if(I % 2) //左子树
				k <<= 1, I = (I + 1) >> 1; //第几个进入左子树
			else //右子树
				k = (k << 1) + 1, I >>= 1; //第几个进入右子树
		printf("%d\n", k);
	}
	return 0;
}