計算位元為1 的個數

計算機概論是一門令人又愛又恨的科目，它的內容可謂包羅萬象。遇到考試時，事前需
要花很多時間準備，才能拿到高分。在學習的內容中，有個章節是數字系統轉換，內容是將
一個十進位的數字，轉換成二進位的數字。現在請你設計一個程式，計算由十進位數字轉換
的二進位數字中，位元等於1 的個數。

輸入說明：
第一行的數字，代表有幾個十進位的數字。第二行開始的每一行，為一個十進位數字，
其範圍為[0, 2147483647]的整數。

輸出說明：
對輸入的十進位數字，以一行分別輸出轉換成二位進數字中，位元等於1 的個數。

輸入範例：
2
1027
65535

輸出範例：
3
16

98 學年度商業類科學生技藝競賽第五題

求餘數

求餘數

求餘數對於會寫程式的人來說，是個簡單的問題，例如用VB 來求餘數時，可以用mod這個關鍵字來實作。但如果算式為R = B^P mod M 的型態，給B、P、及M，要算出餘數R，當B 或P 很大時，那就變得不簡單了。現在，請你設計一個程式，來解決上述這個不簡單的問題。

輸入說明：

第一行的數字，表示有幾個問題要求解，第二行開始的每一行，為一個獨立的問題。每一行包含三個數字，分別為B、P、及M，例如：10 2009 9 代表B=10、P=2009、M=9。所有數字均為正整數，其範圍屬於[1,100000]。

輸出說明：

對輸入的每個問題分別以一行輸出餘數R。

輸入範例：

2
10 2009 9
2 99 5

輸出範例:
1
3

國際資訊奧林匹亞獎牌計算

參加國際資訊奧林匹亞(IOI)競賽者大約有一半的選手可以獲得獎牌。In_d.txt即為被評為可以獲獎的名單（第１欄為國家代碼，第２欄為選手姓名，第３欄為其成績），在此名單中，金、銀、銅牌的分配約為１：２：３。試寫一程式依得分高任分配獎牌。輸出包括四部分：
由高至低排序，並將得獎類別寫在分數旁[G(金)、S(銀)、B(銅)]( 如輸出範例1)。
獎牌分配，即獲得金、銀、銅牌的個數 (如輸出範例2)。
得獎牌最多的國家，寫出國家代碼及獎牌 (不分類別) 數 (如輸出範例3)。
所有得獎者分數之平均數、最高分、最低分及全距 (即最高分與最低分的差距)(如輸出範例4)。

輸入範例(in_d.txt)：
RSA Bruce Merry 333
HUN Balazs Racz 250
UKR Oleksandr lotko 230
ROM Bogdan Dumitru 360
VIE Nguyen N. Huy 430
SUI Peter Kaufmann 266
CRO Frane Saric 268
ROM Radu A. Stefan 150
BLR Ivan Miatselski 226
AUS Peter Hawkins 225
SVK Jan Senko 210
BUL Svetlin Nakov 208

輸出範例１
VIE Nguyen N. Huy 430 G
ROM Bogdan Dumitru 360 G
RSA Bruce Merr 333 S
CRO Frane Saric 268 S
SUI Peter Kaufmann 266 S
HUN Balazs Racz 250 S
UKR Oleksandr lotko 230 B
BLR Ivan Miatselski 226 B
AUS Peter Hawkins 225 B
SVK Jan Senko 210 B
BUL Svetlin Nakov 208 B
ROM Radu A. Stefan 150 B

輸出範例２
G 2
S 4
B 6

輸出範例３
ROM 2

輸出範例４
263.00 430.00 150.00 280.00

密碼解密

在密碼學裡面有一種很簡單的加密方式，就是把原始資料的每個字元通通加上某一個整數K而得到密碼的字元（原始資料及密碼字元一定都在ASCII碼中可列印的範圍內）。例如若K=2，那麼apple經過加密後就變成crrng了；解密則是反過來做。
輸入說明：第一列為加密的K值，第二列為要解密的列數，第三列及以後就是需要解密的字串。(請參照輸入範例)
輸入範例：test7.txt
7
3
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
輸出說明：對每一測試資料，請輸出解密後的原始資料。(請參照輸出範例)
輸出範例：result7.txt
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.
第 5

保齡球計分板

在世界各地，保齡球是相當受歡迎的運動項目之一，藉著球道上滾動的球，來碰倒球道
上的球瓶，勝負以擊倒球瓶之多寡的計分來判定。請你根據下面的計分規則，寫一個保齡球
計分程式，規則如下：
一、每一局共10 格，依序完成每1 格。
二、每格的分數將累計到下1 格。
三、第1 至9 格之計分：每1 格在2 球以內，將全部10 個球瓶擊倒為原則，分數計
算方式可分為：
1. 全倒(Strike)：第1 球就將全部球瓶擊倒，即完成一格。分數計算分式為10 分，
再加上下2 球的擊倒瓶數。
2. 補全倒(Spare)：第1 球未全倒時，再打1 球將剩餘球瓶全部擊倒。分數計算
方式為10 分，再加下1 球的擊倒瓶數。
3. 打完第 1 球後，第2 球如未將剩餘之球瓶全部擊倒，分數為第1 球加第2 球
擊倒之球瓶數。
四、第10 格計分方法：如果前2 球為全倒或補全倒，可再加打1 球，最多打3 球。
五、計分劃記的符號代表意義如下：
1. 全倒以記號『X』來代表。
2. 補全倒以記號『/』來代表。
3. 數字代表擊倒的球數。
4. 擊倒球數為 0 時以『-』來代表。

舉例來說：
每格擊球 7- 8/ X 8- X X X X X 8/9
分數 7 27 45 53 83 113 143 171 191 210
輸入說明：
第一行的數字，表示有幾個計分板要計分，第二行開始的每一行，為一個獨立的計分板。
每一行包含10 格擊球結果。每格以一個空白作為區隔。
輸出說明：
對輸入的每個計分板，分別計算出後的總分數。
輸入範例：
2
7- 8/ X 8- X X X X X 8/9
X X X X X X X X X XXX
輸出範例：
210
300

進位判斷(已做過)

加法的運算是把2 個整數靠右對齊，然後由右至左，一位一位相加。如果相加的結果大
於等於10 就有進位（carry）發生。請寫個程式來判斷兩個正整數相加時，產生了幾次進位的
情況。
輸入說明：
第一行的數字，表示有幾組測試資料，第二行開始的每一行即為一筆測試資料。每一行
輸入的資料有兩個正整數，以一個空格分開，每個整數的長度均小於100 位數。
輸出說明：
對每一筆測試資料，輸出相加後有幾次進位的次數。
輸入範例：
2
123 456
555 555

輸出範例：
0
3

判斷是否為11 的倍數

給一個正整數n，請寫一個程式，判斷n 是否為11 的倍數？
輸入說明：
第一行的數字，表示有幾組測試資料，第二行開始即為第一筆測試資料。每筆測試資料
為一個正整數，數字的位數，最高有可能到1000 位。
輸出說明：
對每一筆測試資料，輸出是否為 11 的倍數。是的話請輸出1，反之則輸出0。
輸入範例：
2
24841983960
121

輸出範例：
0
1

田鼠與狗

在田野中有一隻田鼠和一隻狗。狗想要吃掉田鼠，而田鼠則要儘速的逃進鼠洞中（田表面有許多鼠洞）。狗和田鼠都不是數學專家，但是也都不笨。當田鼠決定了某一個鼠洞後，就以一定的速度直線的跑去。而狗則非常擅長解讀肢體語言，當他一知道田鼠要往那個洞跑，就以田鼠2 倍的速度直線奔去，想要抓住田鼠。假如狗先到達那個洞，田鼠就會被吃掉，否則，田鼠就可安全逃走。
你必須幫田鼠選一個洞，使他可以逃離狗的魔掌（如果這樣的洞存在的話）。

輸入規範

輸入檔案中包含好幾組測試資料，每組測試資料的第一列有一個整數n 和4 個浮點數x1,y1,x2,y2。n（n £ 1000）代表本組測試資料有多少個鼠洞，4 個浮點數（均介於-10000 及+10000之間）代表田鼠(x1,y1)及狗(x2,y2)的x-y 座標。接下來的n 列，每列有2 個浮點數，代表每個鼠洞的座標。（所有的浮點數都到小數點後3 位測試資料組間有一空白列（請參考輸入範例）

輸出規範

每組測試資料輸出一列。如果田鼠可以逃走，請輸出"田鼠可由(x,y)的鼠洞逃走"。(x,y)是某一個洞的座標。如果田鼠無法逃走，請輸出"田鼠無法逃走"請注意：如果田鼠可以從不只一個洞逃走，請輸出在輸入中最前的洞。

輸入範例(test7.txt)
1 1.000 1.000 2.000 2.000
1.500 1.500
3 2.000 2.000 1.000 1.000
1.500 1.500
2.500 2.500
3.500 3.500
輸出範例(result7.txt)
田鼠無法逃走
田鼠可由(2.500,2.500)的鼠洞逃走

字串處理

給一個字串，請寫一個程式，計算此字串中，英文字元有幾個？
輸入說明：
輸入檔第一行表示有幾組測試資料，第二行開始的每一行即為一筆測試資料，每行最多
有1000 個字元。
輸出說明：
對每一筆測試資料，輸出字串中英文字元的個數。
輸入範例：
2
abc123def456
133adfag3428a2fwqgq2
輸出範例：
6
11

排序

給n 個數字，請把它們由大到小排序好。
輸入說明：
輸入檔含有多組測試資料，每組測試資料有兩行，第一行的數字n 為有幾個數字要排序，
第二行則有n 個整數n ≤ 1000，而每個要排序數字的範圍為[-10000, 10000]間的整數。
輸出說明：
輸出已排序好的數列，每個數字之間用一個空白隔開。
輸入範例：
5
1 2 3 4 5
5
-5 -4 -3 -2 -1
輸出範例：
5 4 3 2 1
-1 -2 -3 -4 -5

數字分解

給一個偶數n，請你將n 分解成兩個質數的和，也就是說，這兩個質數相加的和必須等
於n。
輸入說明：
第一行的數字，表示有幾組測試資料，第二行開始即為第一筆測試資料，每筆測試資料
為一個數字，數字的範圍為[4, 10000]間的偶數。
輸出說明：
對輸入的每筆測試資料，分別輸出 2 個質數，用一個空白做為區隔，請由小到大排列。
輸入範例：
2
12
100
輸出範例：
5 7
3 97

最長共同子序列

給2 個字串，請你輸出他們的最長共同子序列（longest common subsequence）的長度。
也就是說，在這兩個字串各自所有的子序列之中，內容相同而且長度最長的那個子序列。舉
例來說有兩個字串abcdgh 和aedfhr，它們的最長共同子序列為adh，長度為3。
輸入說明：
輸入檔含有多筆測試資料，每筆測試資料為二行字串，每行最多有 1000 個字元。
輸出說明：
對輸入的每筆測試資料，輸出它們最長共同子序列的長度。
輸入範例：
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
輸出範例：
4
3

英文造句

請設計一個英文造句的程式，能將輸入的一些名詞，動詞(名詞及動詞的輸入順序是隨機)組成一些簡單句型。
所謂簡單句型是
主詞+及物動詞+受詞.
注意規則：
a.當主詞是He, She, Mary, John時，動詞要加s.
b.當主詞和受詞是同一類人稱代名詞時，受詞要改成反身代名詞。
I -- me -- myself
He/John -- him -- himself
She/Mary -- her -- herself
They -- them -- themselves
本題造句所需用到的主詞、動詞、受詞全部列出如下：
主詞： I、He、She、They、Mary、John
及物動詞： love、like、see、find
受詞：me、him、her、them、Mary、John
輸入規範
輸入檔案中第一列為一個正整數n，代表有n個英文造句練習。其後n列，每一列為一個英文造句練習，每一列有一個主詞、一個受詞、一個動詞(其順序是隨機)，各個英文字之間以一個或多個空白分隔。注意：n 100。
輸出規範
輸出n列，每一列為一個英文造句之答案。若某個練習中，有多個造句是合於文法的，則需全部在同一列印出，且兩個英文句子之間需印出"或"這個字以示區隔。
輸入範例（test7.txt）
5
I her love
I love her
Mary love John
them see I
love I me
輸出範例（result7.txt）
I love her.
I love her.
Mary loves John. 或 John loves Mary.
I see them.
I love myself.

數字刪除

給n 個數字，請你在這n 個數字中，找出所有重覆出現的數字，並把它刪除。最後計算
刪除後剩餘的數字個數。
輸入說明：
第一行的數字，表示有幾組測試資料，第二行開始即為第一筆測試資料，每行不會超過
100 個數字，每個數字之間用一個空白做為區隔，數字的範圍為[0, 10000]間的整數。
輸出說明：
對輸入的每筆測試資料，分別輸出刪除完後剩下的數字個數。
輸入範例：
2
1 2 3 4 5 6 7 8 9 2 1
2 4 6 8 10
輸出範例：
7
5

數學遊戲

在英國有一個數學遊戲，給參賽者一些正整數和一個目標數，參賽者必須在這些正整數間插入+、-、*或 / 的符號，使得最後計算的結果等於目標數。計算的方式是由左到右，而且不必管運算的優先順序（就是不管先乘除後加減那一套）。
在這個數學運算式中，有三個限制：
1. 正整數出現的次序不可改變，也就是說要與輸入的順序相同。
2. 因為目標數也是一個正整數，所以在運算的過程中，你只有在可以整除的情況下，才可以使用除法。
3. 在運算的過程中，如果你用某一個運算符號，會導致產生的數超出-32000 ～ +32000的範圍，那麼你不可以採用此運算符號（也就是說，在運算的過程中都不允許有超出範圍的數出現）。
輸入規範
輸入檔案的第一列是1個整數n，代表接下來有多少組測試資料。
每組測試資料一列。每列的第一個整數 p（0 < p 100），代表要做運算的數有多少個。接下來有p個正整數，每列的最後一個數(即p+1個)為目標數。所有的數都小於32000，而每個數字間以一個空格分開（請參考輸入範例）。
輸出規範
每列測試資料輸出一列運算式，使得輸入的p個正整數運算的結果等於目標數。如果找不到這樣的運算式，請輸出"無解"。如果有多組運算式可以達成任務，請輸出任何一組均可。請參考輸出範例。
輸入範例（test4.txt）
3
3 5 7 4 3
2 1 1 2000
5 12 2 5 1 2 4
輸出範例（result4.txt）
5+7/4=3
無解
12-2/5*1*2=4

解密

有一訊息如下"The final contest for getting right"
經放置於8*10的陣列中為
The*fina
l*contes
t*for*ge
tting*ri
ght*****
此列之後的資料皆為空白
加密後的資料為"Tlttgh**thecfit*oon*fnrg*it***negr*asei*"
寫一程式可以將加密過的訊息解密(訊息長度不超過80個字元)

計算平均值

給你一組數字，請寫一個程式計算出這組數字的平均值，四捨五入至小數第2 位。
輸入說明：
第一行的數字，代表有幾個問題要求解。第二行開始的每一行，為一個獨立的問題。每
一行的第一個整數為這個問題所屬數字的數目n，其範圍為[2, 100]間的整數。接下來的n 個
整數，分別代表這n 個數字的數值，數值範圍為[1, 100]間的整數。
輸出說明：
對輸入的每個問題，分別以一行輸出平均數，輸出的格式請四捨五入至小數第二位。
輸入範例：
2
5 2 4 6 8 10
3 52 30 61
輸出範例：
6.00
47.67

過橋問題

有n個人想要在晚上過橋，橋上每次最多只能容許兩個人行走。由於全部只有一支手電筒，所以每次兩個人拿著手電筒過橋後，必須有一人再把手電筒拿回來，這樣後面的人才能繼續過橋。
每個人走路的速度不同，過橋所需的時間也因此不同。而每次過橋的那兩個人，其花費的時間以較慢的那個人計算（走的快的當然要等走的慢的，因為只有一支手電筒）。你的任務是寫一個程式，安排這n個人過橋，並使得總共花費的時間最少。
輸入規範
輸入檔案的第一列有一個正整數，代表以下有多少組測試資料。每組測試資料的第一列有1個整數n，代表要過橋的人數（最多不會超過1000人）。接下來的n列，每列有1個整數，代表這n個人過橋所需的時間（秒），這些時間均不會超過100秒。
輸入的第一列與第一組測試資料之間，以及各組測試資料之間均有一空白列（請參考輸入範例）。
輸出規範
每組測試資料輸出的第一列為一個整數，代表這組中n個人過橋所需的最少時間。接下來的列為達到此最少時間的過橋方式。每列有1個或2個整數代表過橋的人（每個人以其過橋所需的時間代表。雖然可能有2人過橋時間相同，但那並不會影響結果）。請注意，過橋的順序是去、回交替的，因為需有一人把手電筒帶回。以第一組輸出為例說明：最少需17秒才能讓這4個人過橋。方式為：1秒、2秒的人先過橋，1秒的回來，5秒、10秒的過橋，2秒的回來，最後1秒、2秒的過橋，所以總共的時間為：2+1+10+2+2=17。
如果有不止一種方式可以達到最少時間，輸出任何一種均可。輸出資料的組間亦請空一列。
輸入範例（test2.txt）
2

4
1
2
5
10

4
1
98
99
100
輸出範例（result2.txt）
17
1 2
1
5 10
2
1 2

299
1 100
1
1 99
1
1 98

圍成正方形

這是個有趣的題目，給你已知長度的n 根棍子，請你試著寫一個程式，把這n 根棍子連

成一個正方形。連接的限制條件如下：

一、棍子只可以用端點來連接

二、不能折斷它

三、每一根棍子都必須使用到

輸入說明：

第一行的數字，代表有幾個問題要求解。第二行開始的每一行，為一個獨立的問題。每

一行的第一個整數為棍子數目n，其範圍為[4, 20] 的整數。接下來的n 個整數，分別代表這

n 根棍子的長度。每根棍子的長度範圍為[1, 100]間的整數。

輸出說明：

對每一個問題以一行輸出，如果所給定的棍子可以連成一個正方形，則輸出1。否則輸

出0。

輸入範例：

2

5 1 3 3 4 5

8 2 5 6 7 1 4 4 3

輸出範例：
0
1

基數排序

將一組資料由小而大或由大而小排序式是資料處理中很重要的工作。有一種排序方法稱為基數排序，它的做法是先排數值的個位數，接著排十位數、百位數，千位數、、、。寫一個程式輸入n 筆的數值，並輸出其排序過程。

輸入說明：第一列為數值個數n，(n介於2~10)。
第二列至第n+1列為各數值。(每個數值最多為三位數)
輸入範例：假定有5筆數值分別為：858、792、459、574、762。實際輸入之檔案內容如下：
實際輸入：(test7.txt)
5
858
792
459
574
762

輸出說明：第一列為未排序前的數值次序。
第二列起為各階段排序的數值次序。

輸出範例：上例中5筆數值的各階段排序的數值次序如下：
未排序前：
858、792、459、574、762
第一次依個位數排序結果：
792、762、574、858、459
第二次依十位數排序結果：
858、459、762、574、792
第三次依佰位數排序結果：
459、574、762、792、858

實際輸出：(result7.txt)
858、792、459、574、762
792、762、574、858、459
858、459、762、574、792
459、574、762、792、858