Problem 1066 --小猴子下落

1066: 小猴子下落

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit][Status][Web Board]

Description

有一顆二元樹,最大深度為D,且所有葉子的深度都相同。所有結點從左到右從上到下的編號為1,2,3,·····,2的D次方減1。在結點1處放一個小猴子,它會往下跑。每個內結點上都有一個開關,初始全部關閉,當每次有小猴子跑到一個開關上時,它的狀態都會改變,當到達一個內結點時,如果開關關閉,小猴子往左走,否則往右走,直到走到葉子結點。

一些小猴子從結點1處開始往下跑,最後一個小猴兒會跑到哪裏呢?

Input

輸入二元樹葉子的深度D,和小猴子數目N,假設N不超過整棵樹的葉子個數,D<=20.最終以 0 0 結尾

Output

輸出第N個小猴子所在的葉子編號。

Sample Input

4 2
3 4
0 0

Sample Output

12
7

HINT

二元樹

Source

[Submit][Status]