a249. 00679 - Dropping Balls
Tags : Divide And Conquer tree
Accepted rate : 561人/802人 ( 70% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-12 22:29

Content

有K個球從一完整二元樹(fully binary tree, FBT)的樹根(root)一個一個往下掉。當這個球遇到非終端節點時,可能往左子樹跑,也可能往右子樹跑,如此直到這顆球到達終端節點(也就是樹葉)為止。至於在非終端節點時球該往左或往右的決定乃是由2個值 true, false 來控制的。如果這非終端節點的現在的值為 false,則球來的時候會往左子樹走,但是這個值會變為 true。如果這非終端節點的現在的值為 true,則球來的時候會往右子樹走,但是這個值會變為 false。請注意:一開始時所有非終端節點的值均為 false。另外,在完整二元樹中所有的節點被依序編號,從上(深度 = 1)到下,由左到右。請參考下圖。

舉例來說,上面的圖為深度為4的完整二元樹。第一顆球往下掉會經過節點1、2、4最後落在節點8中。第二顆球往下掉則會經過節點1、3、6最後落在節點12中。第三顆球往下掉會經過節點1、2、5最後落在節點10中。

給你完整二元樹的深度D以及落下的第I個球,請你寫一個程式算出第I個球落在終端節點的編號。

Input

輸入的第一列有一個整數,代表以下有幾組測試資料。

每組測試資料一列有2個整數D,I(2 <= D <= 20, 1 <= I <= 524288)。

Output
對每組測試資料輸出一列,第I個球落在終端節點的編號。
Sample Input #1
5
4 2
3 4
10 1
2 2
8 128
Sample Output #1
12
7
512
3
255
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <50M
Hint :

大量的測資 不是為了讓你吃TLE,

而是想要你做出 速度很快的程式 !

挑戰自己的極限吧! 

 

* Lucky 貓翻譯 

 

// 2011 / 10 / 16  9:30 暫時調寬時間限制 1s -> 3s 

// 2011 / 10 / 17 12:26 暫時調寬時間限制 3s -> 1s 

// 建議使用 較快的輸出輸入 printf() 和 scanf() 

Tags:
Divide And Conquer tree
出處:
UVa679 [管理者: stanley17112 ... (Stanley) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40967 joccc014@gma ... (czone) a249
想法&思路
176 2024-06-22 00:44
40695 seancai78@gm ... (風月春秋) a249
TLE解決法(C)
184 2024-06-06 16:26
39724 toseanlin@gm ... (Dr. SeanXD) a249
解題思路
279 2024-03-23 10:32
38403 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) a249
348 2023-11-19 11:14
35114 liaoweichen1 ... (M_SQRT) a249
Integer.reverse()
435 2023-05-09 16:35