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個球落在終端節點的編號。

範例輸入 ：

5
4 2
3 4
10 1
2 2
8 128

範例輸出 ：

12
7
512
3
255

測試102-1

在ASCII CODE 中，每個字元需要使用 8 bit來存資料。當檔案只包含0123456789AB 十二種字元時，可二進制重新編碼以節省空間，假設新編碼如下：

表3.2.1

二進制	字元
00	A
01	B
100	0
101	1
1100	2
1101	3
11100	4
11101	5
111100	6
111101	7
111110	8
111111	9

例如編碼10100110001 對應到的字元為 1A2B。在猜數字的遊戲過程中，會選定不重複的數字排列當做答案，再由玩家來猜數字，再算出幾A幾B，其遊戲過程可用表3.2.1的編碼紀錄(答案為何，幾A幾B如何算出，不是這次題目考慮的範圍)。例如玩家猜數字6789，算出(0A0B)，則把這過程6789 (0A0B)以1111001111011111101111111000010001編碼，為了讓選手方便對照剛剛的編碼，我們將6789 (0A0B) 編碼拆解成111100 (6) 111101 (7) 111110 (8) 111111 (9) 100 (0) 00 (A) 100 (0) 01 (B)；

若玩家猜數字1253，算出(2A1B)，這過程1253(2A1B)以表3.2.1的方式編碼紀錄為

101  1100  11101  1101  1100  00  101  01

(輸入檔案會省略空白，空白的存在是為了方便讀題)

輸入說明：

第1行的數字n代表有幾筆資料要測試，而n的值介於1和5之間，之後每行為0和1所組成的編碼字串，字串長度<=34，對應到一次猜數字的遊戲過程。在測試檔案中，每個編碼字串均可正確的對應到編碼表中的編碼。

輸出說明：

從第1行起每行將輸入之編碼字串，轉成玩家猜的數字及其幾A幾B的結果。（輸出英文字均為大寫，選手請注意。數字和其幾A幾B的結果以”,”分開。）

輸入檔案1：【檔名：in1.txt】

4

1111001111011111101111111000010001

101110011101110111000010101

11100110111001011110001

111011100110111100110100

輸入檔案2：【檔名：in2.txt】

2

1011100100111111110000

1011100110111100110001

輸出範例：【檔名：out.txt】

6789,0A0B

1253,2A1B

4321,4B

5234,3A

1209,2A

1234,2B

二元搜尋樹

由使用者輸入 N筆資料，建立一個Binary Search Tree(二元搜尋樹)，再以preorder的方式將資料列印出來 。

Input
N
Output
preorder的順序列印出來的資料

Sample Input
7
4
1
5
12
8
13
11

Sample Output

7
4
1
5
12
8
11
13

    圖例:
                7
              /     \
            4       12
          /   \       /   \
        1     5   8    13
                      \
                      11

密碼驗證與擷取

內容 ： 

  小明參加寒假的冬令營，闖關活動中有一關是猜密碼遊戲。首先關主會給闖關者一組阿拉伯數字組成的字串，闖關者要先判斷它是否是不是真正藏有密碼的字串，藏有密碼的字串有下列特性：
  1.它由阿拉伯數字1,2,3,4,5,6,7,8,9組成，且長度介於10至30字元之間。
  2.它必須是迴文(palindrome)字串，也就是不論從左到右或從右到左都是一樣的字串，它可以是奇數或偶    數個字元。例如：12345654321、3344554433等。
  3.字串中兩兩接連的數字之間，後面的數字一定不會大於前面的數兩唄。例如：22221512222 就不是一個    藏有密碼的字串，因為'5'大於'1'的兩倍。
  當闖關者確定藏有密碼時，只要將字串中的偶數字元挑出，就可以得到密碼順利過關了。舉個例子來說：若輸入的字串是 42643734624 ，雖然它是一個迴文字串，但是字串中的第三個數字'6'大於第二個數字'2'的二倍，第六個數字'7'也大於第五個數字'3'的二倍，所以它就不是一個藏有的密碼字串。另外，若輸入的字串是 423435534324 ，它不但是一個迴文字串，且兩兩接連的數字之間，後面的數字一定不會大於前面數字的二倍，所以它就是一個藏有的密碼字串，而藏在此字串中的密碼就是 424424(密碼由字串中偶數的數字所組成，如此例中畫底線的部分→423435534324)。你可以寫一個程式協助小明快速的解出密碼嗎？

輸入說明 ：

輸入字串只有一行，由阿拉伯數字1,2,3,4,5,6,7,8,9組成，長度介於10至30字元之間。

輸出說明 ：

第一行輸出密碼。輸入字串並非藏有密碼的字串，輸出"INCORRECT"訊息。輸入字串若為藏有密碼的字串，但字串中並無包含偶數，輸出"0"。

範例輸入 ：

輸入範例一： 154321123451 

輸入範例二： 123456777654321

範例輸出 ：

輸出範例一： INCORRECT 

輸出範例二： 246642

VB101正副選手考3_暴力証明題

有個數學証明題，是要証明存在一個3的正整數次方，其十進位展開末3位數為001。
証明的方式當然很數學，這裡請用電腦程式的方式，找出到底是3的n次方的展開末3位數為001。
n的最小值是多少?

VB101正副選手考3_趣味的數字問題2

請看第一個式子如下：
當時筆者是將上式寫在一面黑板上，隨後筆者心血來潮，動手把某些數字擦掉，使其成為下式：
此時筆者身旁剛好有一位數學同好，筆者問他：「數字內應該填什麼呢？」，他頗認真的解了起來，解法很不錯。大概看過他所使用解法後，我也獲得了一些想法。而這件事過了幾天後，筆者也自問：「空格裡面的數字，除了原本等號左邊的132與等號右邊的17寫入可以滿足等式之外，是否還可以填上其他不同的數字呢？」
請將解答輸出於out2.txt，若無其它解，則寫「無」。

VB101正副選手考3_趣味數字問題1

3888 * 2 = 7776
上式的等號兩邊都有一個四位數，注意左邊的3888的後三位數相同，而右邊的7776卻是前三位數相同。因為發現這兩個數的變化頗具特色(本來是後三位相同，乘以2後卻變成前三位相同)，所以這時也突發奇想，問自己這個問題：「上面等式兩邊的四位數，除了原本的3888與7776這一組數，可以構成一組型如(abbb,cccd)的四位數組解之外，是否還有其他的四位數組解呢？」
也就是說，請找出下面包含兩個未知的四位數abbb,cccd的數學式子的解：
abbb *2 = cccd
上面的abbb與cccd加上底線，是強調它們是十進位的寫法。其中，a,c是1~9的正整數，b,d是0~9的整數。為了避免出現像1111×2=2222或3333×2=6666這樣子的例子出現，我們規定a與b不同，且c與d也不同。
請將解答輸出於out1.txt，若無其它解，則寫「無」。