M107a_p01 春夏秋冬
阿華和阿俊玩一個遊戲叫做「春夏秋冬」有四種牌，夏吃春、秋吃夏、冬吃秋、春吃冬，吃到的得1分，其餘不計分
我們以 PMAW分別代表春夏秋冬，阿華和阿俊各發六張牌，阿華的a1~a6、阿俊的b1~b6
a1與b1比、a2與b2比…a6與b6比，問阿華與阿俊各得幾分？
in1.txt
3
AMPWAP MWWPMW
PPMMWA MWAAPW
WMAWPM AWMPWW
in2.txt
3
AMWPWP WMWPMW
PAPMMW AMWAAP
PWMAWP MAWMPW
out.txt
4 1
1 5
3 1
1 1
2 3
3 2
參考解1
M107a_p02 小三數學
每列2個數字，第1個數字k：10~2147483647，第2個數字m：-2147483648~2147483647，
若k的每位數之間可插入1或2個運算符號使結果等於 m ，則輸出YES，否則輸出NO
可插入的符號為{ + , - , * , / }四種}可使用相同的符號，先乘除或加減
假設計算過程，除法需整除才算， 例如 9/6*4=6 不算，因9/6非整數不可以先*4再/6
in1.txt
5
123 4
234 14
24015 16
862 4
22 4
in2.txt
3
1357924680 -626963
334 5
543 345
out.txt
YES
YES
YES
YES
YES
YES
YES
NO
-------輸出註解
12/3
2+3*4
240/15
8-6+2
2+2 或 2*2
1357-924*680
3*3-4 或 3/3+4
NO
參考解2
M107a_p03 組合排列
有一個m位數數字X，最少3位,不含0不重複，選n個{2~m}，所有的組合全排列後，由小至大的第k個是多少
若m=4,x=1357，n=3，則全排列為
(1) 135 (2) 137 (3) 153 (4) 157 (5) 173 (6) 175 (7) 315 (8) 317 (9) 351 (10)357 (11)371 (12)375
(13)513 (14)517 (15)531 (16)537 (17)571 (18)573 (19)713 (20)715 (21)731 (22)735 (23)751 (24)753
輸入每列三個數 x,n,k、輸出全排列的第k個數，如上例x=1357,n=3,k=10則輸出357
in1.txt
2
1357,3,10
1357,3,19
in2.txt
3
543,2,3
123,2,5
2468,3,11
out.txt
357
713
43
31
482
參考解3
M107a_p04 十轉五四三
每列2個數 x,k，其中x為十進位 0<x<1000000，且有可能有小數，若有小數最多3位數；k為3,4,5之一，代表k進位
請將x轉為 k進位，若沒有小數則不印，若有小數最多3位，小數部份的尾0不印
in1.txt
3
123.456 5
2345.678 4
345678 3
in2.txt
3
987654.321 3
87653.125 4
6789 5
out.txt
443.212
210221.223
122120011220
1212011210210.022
111121211.02
204124
參考解4
M107a_P05朋友(高中104北二區-3.b839)
問題描述:當我們到一個新環境時，常常會從和我們有相同個性、喜好或來自相同故鄉的人們開始結交，
我們也會對同姓交或名字相近的人感到熟悉或有好感。 在這道題目中，我們將假設朋友關係是這樣建立的：
(1)若兩個人的名字相似，則兩個人會結為朋友。
(2)若兩個人有共同朋友，則兩個人會結為朋友。
如何定義兩個人的名字相似呢？令兩個人的名字為 S 和 T ，我們說若S(長度為m)和T(長度為n)的
最長共同子字串(Longest common subsequene,LCS)長度不小於min(m,n)/2.0，則S和T相似。 {LCS的定義就省略}
根據上上述的朋友關係，我們可以將一群人分成一個或數個團體，每個團體中的任意兩個人都是朋友，而兩個不同團體中的人則都不是朋友。
現在，請你寫一個程式，輸出最大團體(人數最多)的人數個數。
輸入每列第1個數字k代表一群人共有k個人(最多20人)，接著有這k人的姓名{皆是小寫字母最多20字}，以空白隔開
in1.txt
3
5 abc adb xyzzzz zzzxop xompn
5 abc adb xyzzzz zzzxop xoapd
5 abc adb xyzzzz zzzxop xoape
in2.txt
3
6 abcd adb xyzzzz zzzxop xompn zzzab
6 abc adx xyzzzz zzzxop xoapd xyzaa
6 abdc adb xyzzzz zzzxop xoape xyzz
out.txt
3
5
3
6
5
4
M107a_p06霍夫曼編碼
一篇英數字的文章，若每個字元不壓縮最少一個字元需7位元，用霍夫曼編碼，較常用的字元使用較少的位元編碼，
可以使整個使用的位元數減少。例如「ABCABDABEACDABE」共15個字原使用7位元*15共105個位元，若將編碼改為
A00,B01,C10,D110,E1110,F1111，則只需使用36個位元即可。
每列皆為可列印的ASCII字元，最多100個字元，使用霍夫曼編碼，請問最少可用多少位元表示這列文字？
in1.txt
3
ABCABDABEACDABE
This is a Book.
TO BE OR NOT TO BE?
in2.txt
2
In computer science and information theory, a Huffman code is a particular type of optimal code
CAD,CAI,CAM,CIM,DOG,GOD,ACM,CAT,CAE,CAR,BOOK,DOOR.
out.txt
34
48
53
389
168
M107a_p07最少硬幣數
阿華商店使用阿華幣，其幣值是特定的，給一個正整數問換成最少阿華幣的個數？
例如有6種幣值：{1,2,3,5,15,18}要換48元可以是 18+18+5+5+2要五個硬幣，也可以 18+15+15要三個硬幣
每列給第1個數字k{5~12}代表有k種幣值，接著k個幣值，最後m代表要換m元(1~9999}，輸出最小硬幣數
in1.txt
3
6,1,2,3,5,15,18,48
7,1,3,5,8,12,20,35,100
7,1,3,5,8,12,20,35,123
in2.txt
3
10,1,2,3,10,15,20,25,30,55,88,234
12,1,2,5,8,13,25,40,60,99,123,250,511,9876
8,1,5,12,20,25,35,85,100,466
out.txt
3
5
6
4
22
7
M107a_p08最短路徑長
第1列為圖形各邊的資訊{2節點名及邊長}，節點編碼皆為1個大寫字母，邊長1~99，各邊以逗號隔開
第2列有數組詢問，以逗號隔開，每個詢問給兩節點名稱，問這兩節點之最短路徑的長度，輸出亦以逗號隔開
in1.txt
2
AB11,BC12,CD17,DE13,EA6,AF5,FB9,FD8,EF15,FG1,BG3
EB,CE
RN15,AB9,DR14,AE2,BE4,BF16,CF23,HR25,FG13,GH5,AJ17,JK7,FK12,EJ22,AS8,SM18,SP14,LG6,LF21,GM27,MN11,JL20,PN38
AN,BS,LC
in2.txt
2
AB11,BC12,CD7,DE23,EA6,AF5,FB9,CF13,FD8,EF15
ED,CE
RN15,AB9,BC39,CD41,DR53,AE2,BE4,BF16,CF23,CH43,HR25,FG13,GH5,AJ17,JK7,FK12,EJ22,AS8,SM18,SP14,LG6,LF21,GM27,MN11,JL20,PN38
AN,BS,LC
out.txt
15,27
37,14,42
19,24
37,14,42
M107a_p09最長遞增子序列(LIS)
給一串整數數列a1,a2,....am {m最大100} ，從中任選k個b1,b2,...bk使b1<b2<...<bk，
例: bj的順序仍維持ai的順序， 問最大的k為多少？
例：輸入為6,2,9,8,3,7,10,4,5
可以6,9,10、或6,8,10、 6,7,10、 2,7,9、 … 也可以 2,3,4,5 ：最長數列為 4個
輸入為6,2,9,8,3,10,7,4,13,5
可以6,9,10,13、… 也可以2,3,4,5 ：最長數列為 4個
輸入為6,2,9,8,3,10,7,4,13,5,11
可以 6,8,10,13、 也可以 2,3,4,5,11 ：最長數列為 5個
in1.txt
3
6,2,9,8,3,7,10,4,5
6,2,9,8,3,10,7,4,13,5
6,2,9,8,3,10,7,4,13,5,11
in2.txt
5
1,15,17,13,18,19,6,8,24,4,21,0,3,2,22
26,3,12,27,20,29,28,1,21,15,8,10,18,25,13
29,13,17,26,19,5,10,3,20,11,24,28,27,22,16,4,2,21,14,7
3,28,5,16,15,1,6,23,4,14,2,20,7,25,29,26,24,13,21,12
15,1,13,25,5,17,20,2,27,8,6,26,22,4,21,7,19,29,3,23,10,18,28,12,11
out.txt
4
4
5
7
5
6
7
7
=====註：若加印路徑 且有多個LIS相同，則先出現的優先
4:2,3,4,5
4:2,3,4,5
5:2,3,4,5,11
7:1,15,17,18,19,21,22
5:1,8,10,18,25
6:13,17,19,20,24,27
7:3,5,6,14,20,25,26
7:1,2,4,7,10,18,28
M107a_p10整理牌型
撲克牌的 「大老二」以2最大，然後AKQJT9876543,其中10點以T代表，給你6~13張牌，
請先依花色，每種花色再由大至小排列，花色先黑桃、紅心、方塊、再梅花。
每一列有 6~12個數字，中間以逗號隔開，代表撲克牌的編號：
0~12 spade 的 A234~9TJQK , 13~25 heart的 A234~9TJQK ,
26~38 diamond 的 A234~9TJQK , 39~51 club 的 A234~9TJQK
輸出：先S:,再H:,再D:,再C:，若沒有的花色則不印，請參考輸入輸出範例
in1.txt
2
0,1,2,7,9,13,24,25,32,36,50
12,14,15,22,23,3,39,48,6,8
in2.txt
2
11,16,17,18,20,26,30,31,33,5
19,21,27,28,29,34,35,37,40,45,46,47,49
out.txt
S:2AT83,H:AKQ,D:J7,C:Q
S:K974,H:2JT3,C:AT
S:Q6,H8654,D:A865
H:97,D:2QT943,C:2J987
發表文章
0 意見:
張貼留言