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