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，若無其它解，則寫「無」。

全取排列

題目：

將　Ｎ字串　做全取排列，共有幾種方法?
( Ｎ字串不超過10位 )


範例：(也把所有組合輸出出來)

輸入：　程式寫寫寫寫程式
輸出：　　　 420 

大朋友下樓梯

內容 ： 

傳說，有個遊戲叫做大朋友下樓梯，這個遊戲有三種難度，簡單中等困難。

三種難度的差別是，簡單的難度大朋友一次只能下樓梯 1格

中等的是則是，大朋友一次可以下樓梯 1格或 2格

困難的比較具有挑戰性，大朋友一次可以下 1格、 2格或 3格


現在我們想知道，大朋友有幾種下樓梯的方法可以走到地下k樓

對了，有一個限制是，大朋友不能上樓梯只能下樓梯

輸入說明 ：

給定兩個正整數 t, k ， t代表遊戲難度，值為1~3 分別代表，簡單中等困難。

k則是一個負數，代表地下k樓（0>k>-20）

包含多筆測試資料。

輸出說明 ：

輸出大朋友走到地下K層後的方法數。

範例輸入 ： 

1 -1 

1 -2 

2 -1 

2 -2 

2 -3 

2 -4 

3 -1 

3 -2 

3 -3 

範例輸出 ：

1 

1 

1 

2 

3 

5 

1 

2 

4

99正式 Problem 4-2：

有一天菜攤上有 8種類型商品，包括「肉」、「菜」、「蛋」、「果」、「魚」、「蝦」、「豆」及「菇」，每種產品單項價格由輸入檔輸入。某個前來購買的客人，共有 k元預算，表示客人的總購買金額不可超過 k元。若客人對於每種類型商品只可選擇買一項或不買，在預算之內，客人共有那些購買組合？

輸入說明：第 1行是客人之預算金額 k，其值為整數，並且不超過 5000元。第 2~9行有各商品的品名及單價，中間以逗號隔開。商品單價均為整數，且不超過 200元。

輸出說明：每行輸出一種符合預算的購買組合及其支出總金額，但不輸出「都不買」的組合。輸出資料（購買的商品組合及其支出總金額）間，以至少 1個空白隔開。若購買組合包括多種商品，則商品間不限制是否有空白相隔。選手請依支出總金額由大到小依序輸出，但支出金額相同之資料，其輸出順序不限。

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

90
肉, 65
菜, 45
蛋, 30
果, 75
魚, 80
蝦, 95
豆, 55
菇, 60

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

100

肉, 65

菜, 45

蛋, 30

果, 75

魚, 80

蝦, 95

豆, 55

菇, 60

輸出檔案：【檔名：out.txt】

蛋菇 90
蛋豆 85
魚 80
果 75
菜蛋 75
肉 65
菇 60
豆 55
菜 45
蛋 30

菜豆 100
蝦 95
肉蛋 95
蛋菇 90
蛋豆 85
魚 80
菜蛋 75
果 75
肉 65
菇 60
豆 55
菜 45
蛋 30

99模擬 Problem 4-2

子題2（11%）：如果有一個客人來買這個菜攤的n 項商品，每類商品只能買1 項或不買，請

選手列出所有可能的購買組合。輸出之順序，應依照購買之總金額由高而低依序輸出。

輸入說明：

第1 行有1 個數字，代表n 的值。

第2 行有4 組數字，以逗號隔開，分別表示「肉」、「菜」、「蛋」、「果」每項商品的購買金額。

輸出說明：

每列輸出一組購買組合及其購買總金額，並至少以1 個空白隔開。其輸出方式為：每列均輸

出「肉菜蛋果」字串，但客人「購買」之商品名稱以「小括號」括起來。輸出之順序依購買

之總金額由高而低依序輸出，若有總金額相同者則不限順序。

輸入範例：【檔名：in-4-2.txt】

2

140, 64, 36, 84

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

(肉)菜蛋(果) 224

(肉)(菜)蛋果 204

(肉)菜(蛋)果 176

肉(菜)蛋(果) 148

肉菜(蛋)(果) 120

肉(菜)(蛋)果 100

99模擬 Problem 4：排列組合的應用

Problem 4：排列組合的應用

子題1（11%）：一個菜販有「肉」、「菜」、「蛋」、「果」4 類商品，在菜攤上「分類」排列出售，各項商品可由輸入檔讀入其「每公斤利潤」。有一天，菜販忘了商品在菜攤的排列方式，只知道今天各類商品由左至右出售的「公斤數」，其資料選手也可由輸入檔讀入。在不知道今天商品排列的情況下，請選手將所有的排列方式逐一代入計算，依總利潤之高低順序，由高而低，輸出所有排列方式及其總利潤。

輸入說明：

第1 行有4 組數字，以逗號隔開，分別表示「肉」、「菜」、「蛋」、「果」每公斤的利潤。

第2 行有4 組數字，以逗號隔開，表示今天菜攤由左至右各類商品出售之公斤數。

輸出說明：

依總利潤之高低順序，每1 行輸出1 組排列方式及其總利潤，資料間至少以1 個空白隔開。

若有總利潤相同者，其前後輸出順序不拘。

輸入範例：【檔名：in-4-1.txt】

70, 32, 18, 42

43, 24, 21, 39

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

肉菜蛋果 5794

肉蛋菜果 5752

果菜蛋肉 5682

肉果蛋菜 5644

果蛋菜肉 5640

肉蛋果菜 5572

菜果蛋肉 5492

菜蛋果肉 5420

肉果菜蛋 5392

肉菜果蛋 5362

蛋果菜肉 5184

蛋菜果肉 5154

果肉蛋菜 5112

菜肉蛋果 5072

果蛋肉菜 4956

菜蛋肉果 4916

果肉菜蛋 4860

蛋肉菜果 4764

果菜肉蛋 4746

蛋菜肉果 4650

菜肉果蛋 4640

蛋肉果菜 4584

菜果肉蛋 4556

蛋果肉菜 4500

數列搜尋

有一數列0、1、3、8、21、......，輸入某一順序職，輸出該順序值得實際值，若順序為0代表結束。
輸入範例:
2
4
6
0
輸出範例:
1
8
55

Lotto

內容 ： 正體->简体 
為了呼應台灣電腦彩券的發行，我們再次推出跟組合有關的題目。你在買彩券的時候一定會挑你喜歡的數字吧！（雖然理論上不會增加你的中獎機率，但是你還是會 選擇你的Lucky Number）我們的問題是：假設共有49個號碼，而你必須在你的 k （k>6）個Lucky Number中挑6個號碼作為一張彩券的數字組合。例如：你的Lucky Number的集合是{1,2,3,5,8,13,21,34}以就是說 k=8 ，那麼你就有C(8,6)=28種可能的彩券組合：
[1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34].

你的任務是讀入k以及Lucky Number的集合，然後輸出所有可能的組合。

輸入說明 ：
每筆測試資料一行，每行的第1個整數代表 k（ 6 < k < 1 3 ） 。 接下來的k個整數代表Lucky Number的集合，此集合已經按數字由小到大排好。k=0代表輸入結束。

輸出說明 ：
對每一筆測試資料，輸出其所有可能的組合，每個組合一行。請注意輸出組合的順序需由小到大排列。測試資料之間請空一行。請參考Sample Output。

範例輸入 ：

7 1 2 3 4 5 6 7 
8 1 2 3 5 8 13 21 34 
0
範例輸出 ：

1 2 3 4 5 6 
1 2 3 4 5 7 
1 2 3 4 6 7 
1 2 3 5 6 7 
1 2 4 5 6 7 
1 3 4 5 6 7 
2 3 4 5 6 7 

1 2 3 5 8 13 
1 2 3 5 8 21 
1 2 3 5 8 34 
1 2 3 5 13 21 
1 2 3 5 13 34 
1 2 3 5 21 34 
1 2 3 8 13 21 
1 2 3 8 13 34 
1 2 3 8 21 34 
1 2 3 13 21 34 
1 2 5 8 13 21 
1 2 5 8 13 34 
1 2 5 8 21 34 
1 2 5 13 21 34 
1 2 8 13 21 34 
1 3 5 8 13 21 
1 3 5 8 13 34 
1 3 5 8 21 34 
1 3 5 13 21 34 
1 3 8 13 21 34 
1 5 8 13 21 34 
2 3 5 8 13 21 
2 3 5 8 13 34 
2 3 5 8 21 34 
2 3 5 13 21 34 
2 3 8 13 21 34 
2 5 8 13 21 34 
3 5 8 13 21 34

SOS

內容 ：
由於阿許吹的哨聲根本沒人聽懂，

所以到現在他還是迷失在深山中。

此時，

同樣在深山迷路的小綠跟阿波出現了！ 

小綠說：阿許！原來是你在吹哨！我還想說是什麼奇怪的聲音呢！

阿波說：哈哈你連哨子都不會吹，求救的哨音應該是幾個短音幾個長音吧 ... 順序我也忘了耶！ 

這時三個人拿著哨子不知如何是好，請你幫幫忙吧！

給你 n 個短音 m 個長音，輸出這個哨音的所有吹法。 

輸入說明 ：
每組測試資料包含兩個整數 n, m 。( 0 ≤ n, m ≤ 10 )

輸出說明 ：
請輸出 n 個短音 m 個長音的所有排法，

每組輸出之間保留一空行。 

範例輸入 ：

2 1
3 2 
範例輸出 ：

SSL
SLS
LSS

SSSLL
SSLSL
SSLLS
SLSSL
SLSLS
SLLSS
LSSSL
LSSLS
LSLSS
LLSSS