NYOJ 63 小猴子下落

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

书上说这是个二叉树的问题，同时又给了新的解法。

思路：每个小球都会落在根节点上，因为前两个小球必是一个在左字数，一个在右子树。一般的，只需看小球编号的奇偶性，就能指导它是最终在哪棵子树中。对于那些落入根结点左子树的小球来说，只需知道小球是第几个落在根是左子树里面的，就可以知道它下一步是往左还是往右了。依此类推，直至小球落在叶子上。

如果使用题目给出的I,当I是奇数时，它是往左走的第（I+1）/2个小球；当I是偶数时，它是往右走的第I/2个小球。这样可以模拟最后一个小球的路线。

代码：

#include<stdio.h>
int main()
{
	int n,m,i,k;
	while(~scanf("%d %d",&n,&m)&&(n,m))
	{
		k=1;
		for(i=0;i<n-1;i++)
		{
			if(m%2) 
			{
				k=k*2;
				m=(m+1)/2;
			}
			else
			{
				k=k*2+1;
				m=m/2;
			}
		}
		printf("%d\n",k);
	}
	return 0;
}