ZeroJudge A249: Dropping Balls

同題：UVa 00679 – Dropping Balls

有 K 個球從一完整二元樹 (Fully Binary Tree，FBT) 的樹根 (Root) 一個一個往下掉。當這個球遇到非終端節點時，可能往左子樹跑，也可能往右子樹跑，如此直到這顆球到達終端節點 (也就是樹葉) 為止。至於在非終端節點時球該往左或往右的決定乃是由2個值 true, false 來控制的。

如果這非終端節點的現在的值為 false，則球來的時候會往左子樹走，但是這個值會變為 true。如果這非終端節點的現在的值為 true，則球來的時候會往右子樹走，但是這個值會變為 false。

請注意：一開始時所有非終端節點的值均為 false。另外，在完整二元樹中所有的節點被依序編號，從上（深度 = 1）到下，由左到右。請參考下圖。

ZeroJudge A249 題目解說用圖

舉例來說，上面的圖為深度為 4 的完整二元樹。第一顆球往下掉會經過節點 1、2、4 最後落在節點 8 中。第二顆球往下掉則會經過節點 1、3、6 最後落在節點 12 中。第三顆球往下掉會經過節點 1、2、5 最後落在節點 10 中。

給你完整二元樹的深度 D 以及落下的第 I 個球，請你寫一個程式算出第I個球落在終端節點的編號。

範例測資

範例輸入範例輸出
輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列有2個整數 D 和 I (2 <= D <= 20, 1 <= I <= 524288）。		對每組測試資料輸出一列，第 I 個球落在終端節點的編號。
5
4 2
3 4
10 1
2 2
8 128		12
7
512
3
255

解題思路

跑一個 D 的 For迴圈，當 L 是偶數時就是往右走 (目前位置*2+1)，然後 L/=2。如果 L 是奇數的話就是往左走 (目前位置*2)，然後 L = L/2+1。輸出最後的位置即可。

範例程式碼－ZeroJudge A249: Dropping Balls

#include <iostream>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int D, L;
        cin >> D >> L;
        int pos = 1;
        for (int j = 0; j<D; j++)
        {
            if (L % 2 == 0)
            {
                L /= 2;
                pos = (pos*2)+1;
            }
            else
            {
                L = (L/2)+1;
                pos *= 2;
            }
        }
        cout << pos/2 << "\n";
    }
}

//ZeroJudge A249
//Dr. SeanXD
標籤

相關文章

發佈留言