# 【題解】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)

```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