[UVA] 679 - Dropping Balls

題意:
有一棵full binary tree，
從根節點開始，
從左到右，由上到下，
編號1到n，
且每一個節點都為開關都為false。

現在從根節點每放一顆球，
如果求經過該節點開關為false則往左子節點去，若為true則往右子節點去，
而該節點的開關就會相反，
球跑到葉子節點停止。

輸入樹的深度 d 與 i 顆球，
輸出第 i 顆球落在編號多少。

--------------------------------------------------

方法:
模擬操作會超時，
我是推出規律，
直接在輸入前建表，
再依照輸入去查表，

應該有更直覺的方法!

另外一個小發現! 若 i 為奇數則必會落在左子樹，若為偶數必會落在右子樹。
--------------------------------------------------

/* 20150824
 * hanting
 * UVa 679 - Dropping Balls
 * C++
 */
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector<int> table[21];
vector<int> ans[21];
vector<int> ID[21];
void initial()
{
    int id=1;
    for(int i=0;i<20;i++)
    {
        table[i].resize(1<<i);
        ans[i].resize(1<<i);
        ID[i].resize(1<<i);
        for(int j=0;j<ID[i].size();j++)
        {
            ID[i][j]=id++;
        }
    }
    ans[0][0]=ID[0][0];
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<table[i].size();j++)
        {
            if(j&1)
            {
                table[i][j]=table[i][j-1]+(1<<i-1);
            }
            else
            {
                table[i][j]=table[i-1][j/2];
            }
            ans[i][table[i][j]]=ID[i][j];
        }
    }
}
int main()
{
    initial();
   // freopen("1.txt","r",stdin);
    int N;
    while(cin>>N and N!=-1)
    {
        int depth,ballN;
        for(int i=0;i<N;i++)
        {
            cin>>depth>>ballN;
            cout<<ans[depth-1][ballN-1]<<endl;
        }
    }
    return 0;
}