【題解】ZeroJudge a249: 00679 – Dropping Balls

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a249
【解題想法】二元樹 (binary tree)

  • 觀察球的路徑。
  • 【例】第 5 顆球的路徑為 左左右 / LLR (= b’001),bit reverse 後為 b’100。(b’100 + 1) = b’101。
  • 【解法】把球的編號減 1 (zero-based),每次取其二進位表示式的最低位元,用來決定路徑。 從 root (pos = 1) 開始,遇到 0 往左走 (pos = pos * 2),遇到 1 往右走 (pos = pos * 2 + 1)。
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, D, I;
    cin >> T;
    while (T--){
        cin >> D >> I;
        I--;
        int pos = 1;
        for (int i = 1; i < D; i++){
            if (I % 2) {
                pos = pos * 2 + 1;
            } else {
                pos = pos * 2;
            }
            I >>= 1;
        }
        cout << pos << "\n";
    }
    return 0;
}

另一個寫法

#include <iostream>
using namespace std;

long long t, d, n;
long long ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> d >> n;
        n--;
        d--;
        ans = 1;
        for (int i = 0; i < d; i++){
            ans <<= 1;
            if (n & (1LL << i)) ans |= 1;
        }
        cout << ans << "\n";
    }
}

Python code (credit: Amy Chou)
在ZeroJudge上,範測通過,實測TLE。改用Virtual Judge可以AC,連結在此

T = int(input())
for Case in range(T):
    D, I = map(int, input().split())
    idx = 1
    remainder = I
    for i in range(D-1):
        if remainder % 2 == 1:
            # go left
            idx = 2 * idx
            remainder = (remainder + 1) // 2
        else:
            # go right
            idx = 2 * idx + 1
            remainder = remainder // 2
    print(idx)
import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
for i in range(1, T+1):
    D, I = map(int, lines[i].strip().split()) 
    print(int("1" + f"{I-1:0{D-1}b}"[::-1], 2))
分享本文 Share with friends