解題區►Uva

Uva 679 - Dropping Balls

題目

Problem#

有 $K$ 顆球從一顆有高度 $D$ 的完全二元樹上落下，從根節點一直落到葉節點，其中「非葉節點」都儲存個 bool 值(一開始是 false)，當一顆球經過該節點時，就會反轉該 bool 值。當每顆球經過該「非葉節點」時，如果 bool 值是 false，則走左子樹；反之，如果 bool 值是 true，則走右子樹。 問你寫程式回答當第 $I$ 顆球最後停在的節點 $P$ 是多少?

$2 \le D \le 20\text{, and } 1 \le I \le 524288$

輸入#

1
2
3
4
5
l           # 有 l 筆測資
D_1 I_1     # 第一筆測資
...
D_l I_l     # 第一筆測資
-1          # 結尾

輸出#

第 $I$ 顆球最後停在的節點

想法#

  • 對於每個非葉節點 $k$ 來說，經過它的第 $i$ 顆球，往哪方向落下可以直接看 $i$ 是奇數還是偶數: 奇數=左子樹,偶數=右子樹
    (這點可以從落下的規則看出來，初始值是 false，所以奇數會往左子樹，偶數會往右子樹走，找個小值自己模擬一遍就可以觀察出來)
    • 對於 $k$ 的左子節點來說，這顆球是經過它的第 $\frac{i+1}{2}$ 顆球
    • 對於 $k$ 的右子節點來說，這顆球是經過它的第 $\frac{i}{2}$ 顆球
  • 知道了這個規律後就不用一顆一顆模擬了，可以直接模擬第 $I$ 顆落下的情況

AC Code#

https://github.com/roy4801/solved_problems/blob/master/uva/679.cpp?ts=4