2011-10-16 09:36:53Morris
a249. Q679: Dropping Balls
a249. Q679: Dropping Balls
內容 ：
有 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個球落在終端節點的編號。
輸入說明
：
輸入的第一列有一個整數，代表以下有幾組測試資料。
每組測試資料一列有2個整數D,I（2 <= D <= 20, 1 <= I <= 524288）。你可以假設I不會超過終端節點的數目。
輸出說明
：
對每組測試資料輸出一列，第I個球落在終端節點的編號。
範例輸入 ：
5 4 2 3 4 10 1 2 2 8 128
範例輸出 ：
12 7 512 3 255
提示
：
背景知識：
Divide And Conquer | TREE
大量的測資 不是為了讓你吃TLE，
而是想要你做出 速度很快的程式 !
挑戰自己的極限吧!
* Lucky 貓翻譯
出處
：
Uva ACM Q679
(管理：stanley17112000)
作法解釋 : by http://glennchen1.blogspot.com/2009/02/q679-dropping-balls.html
作法解釋 : by http://glennchen1.blogspot.com/2009/02/q679-dropping-balls.html
這題要用 binary 來想
假設 level = 4, times 可能 1~8 但會減1 就是 0~7
times binary system position
位數
012
0 1000 + 000 8+0
1 1000 + 100 8+4
2 1000 + 010 8+2
3 1000 + 110 8+6
4 1000 + 001 8+1
5 1000 + 101 8+5
6 1000 + 011 8+3
7 1000 + 111 8+7
/**********************************************************************************/
/* Problem: a249 "Q679: Dropping Balls" from Uva ACM Q679 */
/* Language: C (353 Bytes) */
/* Result: AC(812ms, 300KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-16 09:26:23 */
/**********************************************************************************/
#include<stdio.h>
int reverse(int D, int I) {
static int i, tmp;
D-=2, I--;
for(i = 0, tmp = 0; i <= D; i++) {
tmp |= (((1<<(D-i))&I) != 0) << i;
}
return tmp;
};
int main() {
int t, D, I, pos;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &D, &I);
pos = 1 << (D-1);
printf("%d\n", pos + reverse(D, I));
}
return 0;
}