ZeroJudge A249: Dropping Balls

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行，每行有兩個正整數D和L，分別代表要跑幾層及有幾顆球。當球遇到非終端節點時，可能往左子樹跑，也可能往右子樹跑，如此直到這顆球到達終端節點（也就是樹葉）為止。至於在非終端節點時球該往左或往右的決定乃是由2個值 true, false 來控制的。如果這非終端節點的現在的值為 false，則球來的時候會往左子樹走，但是這個值會變為 true。如果這非終端節點的現在的值為 true，則球來的時候會往右子樹走，但是這個值會變為 false。一開始時所有非終端節點的值均為 false。要求輸出最後會跑到的節點位置。

範例輸入 #1

5

4 2

3 4

10 1

2 2

8 128

範例輸出 #1

12

7

512

3

255

解題思路

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

解題程式碼如下 (僅供參考)：

#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";
    }
}