【UVa 679】Dropping Balls（小球下落）

Description

有一棵二叉樹，最大深度為D，且所有的葉子深度都相同。所有結點從上到下從左到右編號為1，2，3，…，2eD-1。在結點1處放一個小球，它會往下落。每個結點上都有一個開關，初始全部關閉，當每次有小球落到一個開關上時，它的狀態都會改變。當小球到達一個內結點時，如果該結點的開關關閉，則往上走，否則往下走，直到走到葉子結點，如下圖所示。
   

Input & Output

一些小球從結點1處依次開始下落，最後一個小球將會落到哪裡呢？輸入葉子深度D和小球個數I，輸出第I個小球最後所在的葉子編號。假設I不超過整棵樹的葉子數；D<=20。輸出最多包含1000組數據。
Sample Input
4 2
3 4
10 1
2 2
8 128
16 12345
Sample Output
12
7
512
3
255
36358

#include<cstdio>
#include<cstring>
#define MAX 20
int s[1<<MAX];                    //1<<MAX 即是 2MAX ，最大節點數為 2MAX-1
int main(void)
{
    int D,I;
    while(scanf("%d%d",&D,&I)==2) // ==2 的意思是：如果D和I都被成功讀入，那麼scanf的返回值為2
    {
        memset(s,0,sizeof(s));    //開關，初始全設置為0（預設關閉）
        int k,i,n=(1<<D)-1;       //n是最大結點數
        for(i=0;i<I;i++)          //連續讓I個小球下落
        {
            k=1;
            for(;;)
            {
                s[k]=!s[k];              //狀態改變公式，1和0的相互轉換
                k = s[k] ? k*2 : k*2+1;  //
                if(k > n) break;         //落出界了
            }
        }
        printf("%d\n", k/2);             //“出界”之前的葉子編號
    }
    return 0;
}

分析
① 對於一個結點k，它的左結點，右結點的編號分別是2k和2k+1。
② 儘管每次小球都是嚴格下落D-1次，但上述代碼中採用 if(k>n) break 的方法判斷“出界”更具一般性。
③ 該程式運算量太大：由於I可以高達2^(D-1)，每個測試數據下落總層數可能會高達2¹⁹*19（即I*19）=9961472，而一共可能有1000組數據。