UVa679 - Dropping Balls (tree)

題目大意：

有一顆二元樹，每次走訪會經過走訪次數最小的 node直到leaf node
試問在經過 x 次走訪後將會走到哪個 leaf node ?

分析:

1. 寫樹模擬 -> TLE!
2. 依循規則找出規律 -> AC!

舉例： 假設 D 為 3 , I 為 3

     1                 
   /   \               
  2     3              
 / \  /  \             
4  5  6  7

node	1	2	3	4	5	6	7
num of time 1	T	T		T
num of time 2	T		T			T
num of time 3	T	T			T

看得出來嗎?

在深度為 2 時:
當 I 為奇數時， 必定會經過數字 2
當 I 為偶數時， 必定會經過數字 3

已此類推，找到它的規律了!

                                        奇數則往左邊
                                     ↗
我每次將 I /2 後商數為 
                                     ↘
                                        偶數則往右邊

但要記住的是，當 I /2 = 奇數時，之後在實際走訪時 要變成 (I + 1) /2 以預防 ( I = 1 ) / 2 = 0 的冏境
(會導致每一次的走訪都會走至另一邊)

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL

using namespace std;

int main()
{
    int intCase , D , I , intNow ;
    cin >> intCase ;
    while(intCase--){
        cin >> D >> I ;
        intNow = 1 ;
        for(int i = 1 ; i < D ; i++){
            if(I % 2 ){
                intNow = intNow * 2 ;
                I = (I+1) /2 ;
            }
            else{
                intNow = intNow * 2 +1 ;
                I /= 2 ;
            }
        }
        cout << intNow << '\n' ;
    }
    return 0;
}