【題目敘述】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))