八十八學年度台北市高中資訊學科能力競賽

　

程式設計測驗

　

試卷編號：

　

　

准考證號碼:

下表為評分用，請勿填寫

題目

lostcar

shape

matching

drug

path

第一組

 　 　 　 　 　

第二組

 　 　 　 　 　

第三組

 　 　 　 　 　

第四組

 　 　 　 　 　

第五組

 　 　 　 　 　

總分

 　 　 　 　 　

總得分

注意事項

  1. 所有程式、執行檔、輸入檔、輸出檔之檔名及路徑皆有指定如下表，請務必嚴格遵守，如果路徑或檔名錯誤則以零分計。

  1. 依下表建立目錄並將可執行檔置於指定之相關目錄。

2、在程式內依下表規定寫入輸入檔之路徑及檔名，並將輸出資料寫至下表指定之路徑及檔案中。

  1. 評分採電腦線上自動評分，因此所有程式需遵守題目上所規定之輸入檔、輸出檔格式。

  2. 比賽結束後，立即與一位評審共同進行測試、評審作業。每一題皆有若干測試檔，每一測試檔可占不同分數比例。

  3. 範例磁片內有5個檔案，分別為各題目之範例輸入檔。可以用來測試程式輸入格式是否正確。

a:\lostcar\input.txt

a:\shape\input.txt

a:\match\input.txt

a:\drug\input.txt

a:\path\input.txt

題目

lostcar

shape

matching

drug

path

目錄

C:\lostcar

C:\shape

C:\match

C:\drug

C:\path

可執行檔

C:\lostcar\lostcar.exe

C:\shape\shape.exe

C:\match\match.exe

C:\drug\drug.exe

C:\path\path.exe

輸入檔

C:\lostcar\input.txt

C:\shape\input.txt

C:\match\input.txt

C:\drug\input.txt

C:\path\input.txt

輸出檔

C:\lostcar\output.txt

C:\shape\output.txt

C:\match\output.txt

C:\drug\output.txt

C:\path\output.txt

總分

100

100

100

100

100

　

竊車問題 (Lostcar)

問題敘述

一位警察發現了一些可疑的機車，為了查明這些可疑的機車是否為失竊機車，他需將這些機車的車號與警政署的失竊機車檔案比對。請寫一程式來幫助這位警察找出哪些是失竊的機車。

條件限制

  1. 警察發現的可疑機車不超過20輛。

  2. 警政署的失竊機車檔案中最多為100輛機車資料。

輸入檔格式 (c:\lostcar\input.txt)

第一行有兩個整數n和m，中間以一個空白分開。n為發現的可疑機車數目，m為失竊機車檔案中機車的數目。接下來的n行，每行有一可疑機車的車號，車號以六個字元表示。再接下來的m行，則為失竊機車資料，每行有三項資料，各項資料間以一個空白隔開；第一項資料（欄位1~6）為機車車號，第二項（欄位8~13）為該車外觀顏色，第三項（欄位15~20）為該車車主姓名。

輸出檔格式 (c:\lostcar\output.txt)

請依車主姓名的順序（英文字母由A~Z）依序印出找到的失竊機車資料。若無法找到任何失竊機車請印出 “Cannot find!”。

輸入範例

4 6

PIG222

WIN555

SAD321

JOY866

DOG999 RED CHANG

JOY355 BLUE LEE

SAD321 YELLOW WANG

FOX555 WHITE WU

WIN555 BROWN HO

PIG222 BLACK LIN

輸出範例

WIN555 BROWN HO

PIG222 BLACK LIN

SAD321 YELLOW WANG

形狀問題 (shape)

問題敘述

某販賣積木玩具公司為了慶祝十週年紀念，於度假村舉行慶祝酒會，並於會場不同地點的正方形水泥地上，利用填滿聖誕紅花盆的方式，佈置出不同的幾何形狀。有一個盲人，很想知道某個地點佈置的形狀，請你幫他做成點字板，並將結果顯示出來，其中有花盆的地方用"*"代表，水泥地則用"0"代表。請寫一個程式，判斷點字板上所表示的花盆組成形狀為何。

條件限制

  1. 點字板邊長N最少為2最多為30。
  2. 形狀一定為凸多邊形，且最多為十邊形。

輸入檔格式 (c:\shape\input.txt)

第一行為一正整數N，表示一個N88informN的資料矩陣；接下來的N行顯示地面上的狀況，"0"表示水泥地，"*"表示有花盆的地方，每個檔案，只有一個相連整體的形狀。

輸出檔格式 (c:\shape\output.txt)

請列出此佈置地點的形狀名稱，例如：三邊形、四邊形、五邊形…等等。

輸入範例

8

00000000

00*00000

0****000

*******0

00****00

00000000

00000000

00000000

輸出範例

五邊形

緣份問題 (Matching)

問題敘述

胡孝啟與女友方月花學了一個計算兩人緣份的方法，就是將兩人姓名中每個字的筆劃穿插排成一排，男生的名字先放，也就是若男生名字以男1 男2 男3三個字表示，女生名字以女1 女2 女3表示，則放筆劃的順序為男1女1男2女2男3女3（如下圖最上面一層之數字，胡孝啟三個字比劃分別為9,7,11，方月華為4,4,8，則先將這六個數排成 9474118）。然後兩個兩個相鄰數字相加後取個位數，形成第二層，這樣一層一層累加到最後剩下兩位數字即停，此兩位數就是他倆的緣份評分。例如：下圖第二層為9+4=13取個位數3, 4+7=11取1, 7+4=11取1, 4+1=5, 1+1=2, 1+8=9，算完後形成311529。以此類推，他倆的緣份計算方法就如下圖，最後得到52分。

88inform請你設計一程式，讓佳偶只要輸入姓名筆劃之排列（如9474118），電腦就能自動計算出他倆的緣份分數。

輸入檔格式 (c:\match\input.txt)
檔案中第一行為測試對數，第二行為第一對男女比劃之排列，第三行為第二對男女比劃之排列，以此類推。

輸出檔格式 (c:\match\output.txt)

請由檔案輸出各對配對分數，每對以一行顯示。

輸入範例：

3

9474118

4112010139

101411579

輸出範例：

52

96

04

藥品煉製問題 (Drug)

問題敘述

你是一個煉金術士，平常以採集藥材、煉製成藥品販售之所得維生。主要採集的原料有：熔岩、木柴、泉水、及藥草。在煉製藥品的過程中可生產三種半成品：硫黃、蒸餾水、及毒花。煉製完成後販售的藥品則有：炸藥、麻醉藥、解毒丸、及金創藥。

表一. 製造各種半成品及藥品所需的材料及數量。

　

熔岩

木柴

泉水

藥草

硫黃

蒸餾水

毒花

硫 黃

2

1

1

 　 　 　 　

蒸餾水

 　

1

2

 　 　 　 　

毒 花

 　 　

1

1

 　 　 　

炸 藥

 　

1

 　

1

4

 　 　

麻醉藥

 　

1

 　 　

1

2

2

解毒丸

 　

2

 　

2

 　

1

1

金創藥

 　

1

1

5

1

 　 　

近來由於供需失調，造成市場價格波動，你希望趁著高價，多製造一些藥品出售。然而，你只能憑藉手中的原料，儘量製造高價藥品，以獲取最大的利潤。因此，請你撰寫一個程式，評估手中的原料及市場的藥品價格，並決定出各藥品的產量，以獲取最大的利潤。

條件限制

  1. 每一原料的數量介於0~99之間。
  2. 每一藥品的價格介於0~999之間。

輸入檔格式 (c:\drug\input.txt)

第一筆輸入四個數字，分別為目前手中的熔岩、木柴、泉水、藥草等原料的數量，數字間以一個空白分開。

第二筆輸入四個數字，分別為目前炸藥、麻醉藥、解毒丸、金創藥等藥品的價格，數字間以一個空白分開。

輸出檔格式 (c:\drug\output.txt)

由於目的是獲取最大的利潤，因此每一種藥品做了幾個並不重要，只要能賣得最多錢就好了。因此，請輸出製造完成之藥品出售後的「最大利潤」之金額。

輸入範例

8 8 8 4

400 300 200 100

輸出範例

可獲取的最大利潤：600元

路徑問題 (path)

問題敘述

在一個古老的舊城市裡，所有的道路皆是單行道。但因其道路缺乏規劃，故某些單行道所連接之路口可能完全相同且方向一樣。甚至於有單行道其起始路口與終點路口是同一個路口。為了發展該城市之觀光事業，該市交通局決定重新規劃所有道路。但首要任務則必須先了解各路口之間可以通行之路徑數。請寫一個程式計算任意兩個路口之間有多少種不同的路徑。一個路徑是由一個(含)以上不重複之單行道所組成(單行道、起始路口、終點路口皆不可重複，但其餘路口可以重複)。

條件限制

  1. 路口數n最少為1最多為50，且路口編號由1 至 n。
  2. 單行道數量m最少為1最多為2500。

輸入檔格式 (c:\path\input.txt)

第一行有兩個整數n 和 m，以一個空白分開。接下來的m行各有兩個整數，分別代表各單行道之起始及終點路口。

輸出檔格式 (c:\path\output.txt)

請以一個 n x n (n行 n列)的矩陣，列出從路口i至路口j之路徑數，1<= i, j <= n。每一列i均應有n個整數，分別代表路口i至所有其它路口之路徑數。在同一列的數字請以一空白隔開。

輸入範例

5 6

1 1

1 2

2 3

4 3

5 4

5 4

輸出範例

1 2 2 0 0

0 0 1 0 0

0 0 0 0 0

0 0 1 0 0

0 0 2 2 0