UVa 679 - Dropping Balls

題目簡述

有一個滿二元樹，題目會多次的從樹根放球往下掉
每個節點都有一個標記，一開始初始值是往左，當有一顆球經過時，就會切換成右，再有一顆球經過，就切換成左，以此類推
當一顆球來到一個節點，依照標記來決定要往左子樹走，還是右子樹走，來走到下一層
一顆球走到最下面那層，就會有最後停下來的那個節點編號，然後就可以從樹根放下一顆球
題目會給定最大深度 $D$ 和總共放了 $I$ 顆球
輸出第 $I$ 顆球最後會停在哪個節點

解題想法

可以開一個陣列存二元樹，然後依序模擬每一顆球往下掉的過程和結果，最後輸出答案，不過這樣可能會 TLE
若是可以給定第 $I$ 顆球，直接計算就會快很多
想法
1. 若是數字是奇數，那應該往左走，若是偶數則往右走
2. 每往下走一層，數字應該要除以二
所以就用一個 for 迴圈掃過每一層，然後每一層決定要往左走還是往右走
注意若此節點編號為 $N$，則下一層左邊節點編號為 $2N$，右邊節點編號為 $2N+1$

程式碼

/*****************************************
  Filename:p679.cpp
  Author:Willy Chen(willychen.org)
  Date:2019.09.30
*****************************************/
#include<iostream>
using namespace std;

int main(){
    int kase;
    cin >> kase;
    while(kase--){
        int D, I;
        cin >> D >> I;
        int now = 1, remain = I;
        for(int i = 1; i < D; ++i){
            if(remain % 2 == 1){
                // Left
                now = 2 * now;
                remain = (remain + 1) / 2;
            }else{
                // Right
                now = 2 * now + 1;
                remain = remain / 2;
            }
        }
        cout << now << endl;
    }
    return 0;
}