UVa 679 - Dropping Balls

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

球從樹根開始向下，如果節點為 true ，球則往右，反之往左。問最後到達的葉節點為多少？

Solution

本來是用模擬的，不過會超時。想從數列中找出個規律，但不得要點，後來查了一下，使用二進位來解決。

很明顯最小值會是 1 << (depth-1) ，也就是最左邊的葉節點。接著觀察增加的數字，這邊假設深度為 5 :

10000 = 16

(次數)      (增加的數字)
1 = 0001    1000 = 8 
2 = 0010    0100 = 4
3 = 0011    1100 = 12
4 = 0100    0010 = 2
5 = 0101    1010 = 10

. = ....    .... = ..

15 = 1111    1111 = 15

-----------------------
ex. 10000 + 1000 = 11000 = 24

可以看出增加的數字，轉為二進位後，將會是次數二進位的反向，實際上我們也可從二元樹的結構發現這件事(雖然我一開始沒看出來就是了…)。
第 1 次的為 1<<(5-1) 也就是 16,第二次為 16 + 8 = 24，此數列為: 16, 24, 20, 28, 18, 26, …, 31。

至於要如何將二進位顛倒，簡單的寫法，bit 為總位數:

unsigned int tar = 0;
while (bit--)
{
    tar <<= 1;//將目前存好的左移一位
    tar |= (n & 1);//將 n 的最後一位加到 tar
    n >>= 1;//n 移掉最後一位
}

p.s. 記得要使用 unsigned int 才不會有負數的問題

Code

UVa 679UVa 679 - Dropping Balls

#include<cstdio>

inline unsigned int reverse_bits(unsigned int n, unsigned int bit);//將 n 的二進位顛倒，bit 為總位數
int main()
{
    int Case;
    scanf("%d", &Case);

    while (Case--)
    {
        unsigned int depth, n;
        scanf("%d%d", &depth, &n);

        printf("%u\n", (1 << (depth - 1)) + reverse_bits(n - 1, depth - 1));
    }

    return 0;
}
unsigned int reverse_bits(unsigned int n, unsigned int bit)
{
    unsigned int tar = 0;
    while (bit--)
    {
        tar <<= 1;//將目前存好的左移一位
        tar |= (n & 1);//將 n 的最後一位加到 tar
        n >>= 1;//n 移掉最後一位
    }
    return tar;
}