雄中九十学年度全校资讯学科能力竞赛程式设计试题

1、雄中九十學年度全校資訊學科能力競賽程式設計試題比賽注意事項1 你的解答程式必需以題目標題後面括弧內的英文字命名。例如judge,若使用C/C+語言，則你的程式原始碼為judge.c/judge.cpp；使用BASIC，則為 judgabas；使用Pascal,則為judge.paso並請以.exe另存一執行檔，例如 judgaexe。交卷時兩者都需在答案磁片內附上。為了保險起見，請將你所有 的答案再備份在另一張磁片上。2請特別留意每題的輸入、輸出的方式、檔名及格式。 3注意每個題目資料的上下限。4輸出、輸入都以換行符號（enter鍵）作為分段。5每個題目，你的程式必需在 5 秒鐘內跑完。6配分

2、：一至五題每題 10 分，六至七題每題 15 分，每題再分幾個測試值計分。一、獎落誰家 (judge) 國際奧林匹亞資訊競賽的比賽方法如下：在兩天的賽程中，各有三道題目， 滿分各為一百分，合計六百分。在 2001 年的比賽中，冠軍可以獲得一臺筆記型 電腦，亞軍、季軍則可各獲得一隻手機。現在請你寫個程式，計算每個選手的總 成績，並找出前三名。輸入說明：由標準輸入(鍵盤)輸入。第一行有一個正整數 N , 3<=Nv=100，表示共有N 個選手參賽。接下來 N 行，依序表示 1 到 N 號選手的成績。每個人的成績以六 個 0 到 100 的整數表示，分別是六題的得分，彼此以空白隔開。你可以假設

3、前三 名都只有惟一一個。輸出說明：輸出一行到螢幕上。依序為冠、亞、季軍的編號。並以空白隔開。範例輸入：510 0 30 0 40 080 40 10 20 30 10010 0 0 0 0 010 70 20 40 80 10100 30 50 70 60 80範例輸出：5 2 4二、搜尋 DNA(dna)在自然界中，細菌的 DNA 是呈 環狀的。有一種潛溶性病毒，他在感染細菌 時，能將自己的 DNA 注射到細菌體內，並插入細菌的環狀 DNA 中，成為它的 一部份。例如： 某細菌的環狀 DNA 展開後為：ACTTGCATCGA某病毒 DNA 為：GTCAG若它在細菌 DNA 的第三個位置插入則

4、細菌 DNA 展開後變為：ACGTCAGTTGCATCGA科學家們相信，這種插入 DNA 的行為對細菌的生理有很大的影響。現在請 你寫個程式幫忙科學家們找出病毒插入 DNA 的位置輸入說明：由鍵盤輸入，共有兩行。第一行為某疑似被感染的細菌的 DNA ，以一個僅 包含 A、C、G、T 字元的字串表示。第二行為某病毒的 DNA ，表示方法同上。 輸出說明：輸出到螢幕上。若這個病毒有感染此細菌，請輸出它插入的位置，以一個正 整數表示。若無，請輸出 0。你可以假設每個細菌至多只被感染一次，且細菌及 病毒 DNA 的長度皆不大於 100。範例輸入 I ：AGTTGCATCGAACGTCGTCAG範例輸出

5、 I ：14(注意細菌 DNA 為環狀！ )範例輸入 II ：GATACTGATG範例輸出 II ：三、費氏數列 (fibo)著名的數學家 Fibonacci 曾提出一個有趣的兔子問題：飼養一隻幼年的雌兔 和一隻幼年的雄兔，幼兔需一個月的時間長至成年，隨即開始繁殖。成年的雌兔 每個月會生一隻雌的幼兔及一隻雄的幼兔。試問 N 個月後，共有幾對兔子？Fibonacci證明，若我們用F(N)表示N個月後有幾隻兔子，則有：F(0)=1F(1)=1當 N>=2， F(N)=F(N-1)+F(N-2)此即著名的費氏數列。輸入說明：由鍵盤輸入一個正整數N。N的值最大為255。輸出說明：將 F(N) 的

6、值輸出到螢幕上。範例輸入 I ：5範例輸出 I ：8範例輸入 II ：99範例輸出 II ：354224848179261915075四、最快讀取 (read)KSHSeagate公司正在研發一種新的儲存裝置，他們需要你的幫忙來完成一 個關鍵性的程式。這種儲存裝置，是用不同的原子排列成一條線，每個原子代表 一個位元。要讀取這條原子陣列 ，他們用一個探針作前後移動來讀取。很不 幸地，受限於技術問題，這個探針每次動作只能向前移動 F 個單位，或向後移動 B 個單位。一開始，這個探針位於原子陣列的一端 ，我們以坐標 0 表示這個位置。 而這個原子陣列的另一端，我們用 N 表示它的坐標。例如：當 F=

7、4， B=3 ， N=10若我們要讀取位置5的資料，我們可以命令這探針向前移動2次，向後1 次，因為4 + 4-3 = 5。如此我們總共執行了 3次動作。請你寫個程式，找出移動步驟最少的方法。請注意：探針只能在這個原子陣 列內移動，也就是說，在整個移動過程中，探針的位置必需大於等於 0 且小於等 於 N 。輸入說明：由鍵盤輸入一行四個正整數 F、B、N、X，彼此以空格隔開。其中F、B、 N的說明如前述，而X則為所欲移動的目標位置之坐標。你可以假設 X<=N，且 這四個數字最大不超過 1000。輸出說明：輸出一個整數。若探針可以移動到目標上，請輸出最小移動步驟。若不行， 請輸出 0。範例輸

8、入 I ：4 3 10 5範例輸出 I ：3範例輸入 II ：14 6 29 17範例輸出 II ：0五、網路塞車(net)隨著網際網路日漸發達，如何在各伺服器中做最快速的傳輸，已成為一個重 要的課題。為了解決網路塞車的問題，請你寫個程式找出兩臺伺服器中能以最大 頻寬傳輸的路徑。如下圖所示：A 40B 30CD 50E 20 F其中A、B、C、D、E、F表示六臺伺服器，線段表示相連，線上的數字則 表示此網路線的頻寬。傳輸資料時，需以整個路徑中頻寬最小者為實際頻寬。也 就是說，當我們從A往F傳輸資料時，若沿著AF,則實際頻寬為10,若沿著 A D E F，實際頻寬為20;若沿著ABC F，則實際

9、頻寬為30。輸入說明：由檔案net.in輸入。第一行有兩個數字N、M，以空白隔開。表示共有N臺 伺服器，及M條線路。接下來 M行，每行有三個數字P Q W，以空白隔開。表 示P號伺號器到Q號伺服器的頻寬為 W。各臺伺服器皆以1到N編號，任兩臺 之間至多只有一條線路，且線路為雙向的。其中，N<=100。輸出說明：輸出一個整數到螢幕上，表示從1號伺服器傳輸到N號伺服器的最大實際 頻寬。若此二者沒有路徑連結，則輸出 0。範例輸入I :6 71 2 402 3 303 6 704 1 205 4 505 6 201 6 10範例輸出I :30範例輸入 II ：4 31 2 1002 3 1000

10、1 3 10000範例輸出 II ：0六、電阻串聯 (resist)在電路中，串聯各個電阻器可以得到相當於其總和的電阻。例如串聯3Q的電阻器2個和4Q、5Q的電阻器各一個,可以得到總和為3+3+4+5=15Q的電阻。 不過，將電阻器串聯起來需要在電路上焊接且占去一些空間，因此我們總希望能 用最少的電組器串聯來達到所要的電阻值。輸入說明：由檔案resist.in輸入。第一行有兩個正整數N、S,以空白隔開。表示共有N 種電阻器，而所要的電阻為SQ。第二行有N個正整數，表示各類電阻器的值。 在串聯的過程中，各類電阻器所用的個數不限。其中 0<N<=10， 0<S<=1000。

11、輸出說明：輸出到螢幕上。若可以串聯達到所欲的電阻值，則在第一行輸出共需幾個電 阻器，第二行則輸出 N 個整數，依序表示各類電阻器各需幾個。若不只一種最 佳方法，你的程式只需輸出其中一種。若無法達到，則僅輸出一個整數0。範例輸入 I ：3 2181 5 10範例輸出 I ：253 1 21範例輸入 II ：2 3912 22範例輸出 II ：0七、基地台 (phone)KPhone 公司打算在 K 市架設一些基地台，每個基地台的有效範圍都為半徑 R 的圓形區域。他們將全市分成 N 個據點，打算在其中幾個據點架設基地台， 使得對於任一個據點 ，都至少有一個基地台涵蓋它 。不過，架設基地臺花費不小， 且因地而異。請你寫個程式來協助 KPhone 公司找出花費最小的方法。 輸入說明：由檔案phone.in輸入。第一行有兩個正整數 N和R,以空白隔開，表示共 有N個據點，且每個基地台的半徑為 R。接下來N行，每行有三個整數，分別 表示各據點的x座標、y座標和在此建基地台的花費。其中 0<