2012年12月10日 星期一

二元搜尋樹


由使用者輸入 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

2012年12月3日 星期一

密碼驗證與擷取


內容 : 
  小明參加寒假的冬令營,闖關活動中有一關是猜密碼遊戲。首先關主會給闖關者一組阿拉伯數字組成的字串,闖關者要先判斷它是否是不是真正藏有密碼的字串,藏有密碼的字串有下列特性:
  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"。
範例輸入 :help
輸入範例一: 154321123451 
輸入範例二: 123456777654321
範例輸出 :
輸出範例一: INCORRECT 
輸出範例二: 246642

2012年11月25日 星期日

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後卻變成前三位相同),所以這時也突發奇想,問自己這個問題:「上面等式兩邊的四位數,除了原本的38887776這一組數,可以構成一組型如(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,若無其它解,則寫「無」。

全取排列


題目:


將 N字串 做全取排列,共有幾種方法?
( N字串不超過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 
 
範例輸出 :
4

2012年11月24日 星期六

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

2012年11月23日 星期五

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

大樂透中的數學1-完全包牌法

大樂透是從1到49號中,選出6個號碼為一組牌。例如,你可以選擇1,3,5,7,9,11。
從檔案中讀出玩家喜歡的號碼有10個,請輸出這10個號碼組合出所有可能的牌。
在輸出的檔案最後,輸出共有幾組牌。
輸入:in.txt
10,22,31,5,6,11,13,42,1,9

輸出:out.txt
10,22,31,5,6,11
10,22,31,5,6,13
10,22,31,5,6,42
10,22,31,5,6,1
10,22,31,5,6,9
...
共有x組牌

(題外話,完全包牌法是不可行的,下次再來試試所謂的包中3的聰明包牌法,另外還有什麼天才包牌法)

子集合

輸入一變數N,再輸入N 個數字成為一個含有N 個數的集合A, 


然後輸出所有這個A 集合的子集合。 

Ex: N=3, A { 1, 2, 3 } 

ANS: { } <--- 空集合 

{ 1 },{ 2 },{ 3 } 

{ 1, 2 },{ 1, 3 },{ 2, 3 } 

{ 1, 2, 3 }

2012年11月22日 星期四

海星


每個人都有自己的喜歡的東西,而Fuko最喜歡的就是海星了。你沒看錯,請不要對別人的興趣不以為然。



而且善良純真的Fuko秉持著與民同樂的想法,想把快樂散佈到這個世界上,她認為只要讓每個人都有海星,這個世界就可以變得和諧愉快。


所以她利用閒暇時間雕刻木製海星,然後一遇到自己的朋友就把海星硬塞到對方手中。


因為這個木製海星是手工製的,所以每一個海星都不會相同,而Fuko會在送出每個海星前在上面標明自己對於這個海星的滿意度x,x越大代表她對這顆海星越滿意。


為了讓自己的雕刻海星更臻於完美,她會不時的回想起她送出的海星中第k好的滿意度,然後利用自己對於海星的驚人記憶力想起那個海星的優缺點進而改進技術。


只可惜人並不是完美的,雖然Fuko對海星有強大的記憶力,可是看到亂七八糟的數字就舉手投降了,這讓她造成了非常大的困擾,沒有辦法想起滿意度就沒有辦法雕刻出更好的海星,當然也就不能讓這個世界更加和平了!


Fuko的姐姐Kouko知道了Fuko的煩惱,所以特地請你來幫她寫一個程式,可以記錄她送出的海星滿意度,並在適當的時候提醒她目前送出的第k好的海星是哪一個。




輸入說明 :


每行有一條指令依序執行,分別為


GIVE X:代表送出一個滿意度為X的海星             ( 0 < X <= 100000000 )
FIND K:代表回想送出的海星中第K好的滿意度   
END:Fuko累了要去睡覺囉!



輸出說明 :


對於下列三種指令


GIVE X:不輸出
FIND K:輸出Fuko送出的海星中第K好的滿意度
END:不輸出並結束程式






範例輸入 :


GIVE 1
GIVE 3
GIVE 5
FIND 1
FIND 2
FIND 3
GIVE 2
GIVE 4
FIND 1
FIND 2
FIND 3
FIND 4
FIND 5
END 


範例輸出 :


5
3





1

2012年11月21日 星期三

排列組合二


從檔案in.txt第一列讀入排列組合的項目n個,再讀入第二列數字m,從n個項目中,取出m個項目的組合,全部輸出到out.txt中。

PS:X1 與 1X 視為相同物
輸入範例:
a b c 1 x
2

輸出範例:
ab
ac
a1
ax
bc
b1
bx
c1
cx
1x

2012年11月20日 星期二

排列組合

請設計一個程式,可以將一組數字、字母或符號進行排列,以得到不同的組合順序,例如123這三個數的排列組合有:123、132、213、231、312、321六組;或是ABC這三個字母的排列組合有:ABC、ACB、BAC、BCA、CAB、CBA六組。

輸入說明:第一列為要排列的列數,第二列及以後為一組由數字、字母或符號組成的字串。(請參照輸入範例)
輸入範圍:每個數字、字母或符號皆為一個字元,每組最少為3個字元,最多不超過10個,且不重覆。
輸入範例:in.txt
2
213
ABC

輸出說明:輸出不同的組合順序,順序規則如下:請按照字典排序,由左到右,由上到下,由小到大排列。(請參照輸出範例)
輸出範例:out.txt
123
132
213
231
312
321
ABC
ACB
BAC
BCA
CAB
CBA

排列組合一


從檔案 in.txt 讀入排列組合的項目,將所有可能的排列輸出到out.txt。

輸入範例:
a b c 1

輸出範例:

abc1
bac1
cab1
1abc
acb1
a1bc
bca1
b1ac
cba1
c1ab
1bac
1cab
ab1c
ba1c
ca1b
1acb
ac1b
a1cb
bc1a
b1ca
cb1a
c1ba
1bca
1cba

0 與 1 的遊戲


內容 :
有 1 個 bit,可以表示 0 與 1。
有 2 個 bit,可以表示 00,01,10,11。
有 n 個 bit,請產生所有 n 個 bit 所能表示的 2 進位數字。
輸入說明 :
每行一個數字 n ( 0 < n < 15 )
代表 n 個bit
輸出說明 :
請參考範例輸出
範例輸入 :
1
2
範例輸出 :
0
1
00
01
10
11
提示 :
字串是你的好朋友