题目链接：UVa 679
题意：
有一颗二叉树，最大深度为D，且所有叶子的深度都相同。所有的结点从上到下从左到右编号为1，2,3,...，2^D-1。在结点1处放一个小球，它会往下落。每个内结点都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。
输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D<=20。输入最多包含1000组数据。
分析：
那如图所示二叉树来说。
第1个小球的运动路径：1-->2-->4-->8
第2个小球的运动路径：1-->3-->6-->12
第3个小球的运动路径：1-->2-->5-->10
第4个小球的运动路径：1-->3-->7-->14
第5个小球的运动路径：1-->2-->4-->9
……
对于第k个小球：第一步是1，
①如果k是奇数，那么第2步是2=1*2，将k更新为k=（k+1）/2；
- 如果k是奇数，那么第3步是4=2*2，将k更新为k=（k+1）/2；
- 如果k是偶数，那么第3步是5=2*2+1，将k更新为k=k/2；
- ……
②如果k是偶数，那么第2步是3=1*2+1，将k更新为k=k/2；
- 如果k是奇数，那么第3步是6=3*2，将k更新为k=（k+1）/2；
- 如果k是偶数，那么第3步是7=3*2+1，将k更新为k=k/2；
- ……
那么就可以发现规律求第k个小球只需对k奇偶性进行判断，然后每次更新k，直到到达叶子结点。
CODE:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;int t, num, cnt, I, d;int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endifcin >> t;while (t--){cin >> d >> I;cnt = num = 1;while (cnt < d){if (I % 2){I = (I + 1) / 2;num *= 2;}else{I /= 2;num = num * 2 + 1;}cnt++;}cout << num << endl;}return 0;
}