【測驗M09】2000年全國網際網路程式設計比賽高中組初賽題目 [回前頁]
一、傳訊問題
因應時代的進步，阿米巴星球的軍事大樓開始使用網路，來連接辦公室中的每一台電腦。最近他們開始為新架設好的網路系統作一些測試。
然而，測試的結果並不順利。因為兩兩相連的電腦處理速度、傳輸材質、以及傳輸距離不盡相同，有些電腦之間的傳輸速度很快，但也會有兩台電腦之間傳輸速度很慢的情況。軍事大樓最需要的，就是訊息廣播的功能，希望能在最快的時間內，讓所有的電腦都得知某項訊息(例如：有敵國向他們宣戰)，因此這套系統設計成每台電腦可以同時開始向其他n-1台廣播訊息。可是在一開始的設計中，他們忽略了兩兩電腦間傳輸速度不盡相同的問題，因此如果電腦A到電腦B的直接傳訊非常慢，由A發出的廣播，傳輸效率會很差。
後來，他們想到一個新的主意：為了減小訊息傳遞所需的時間，所以訊息有些會用轉送的方式來傳遞，例如說：A到B的訊息可能可以走A到C、C再轉送給B的路徑，而可能可以達到比較好的傳輸效率。
請寫出一個程式協助阿米巴國防部測試這套系統，找出廣播一個訊息所需的最小時間。
輸入檔說明
輸入檔定義了多組各自獨立的測試資料，一組接著一組，每一組的內容如下所述：
第一行為所有電腦的數目n，其中1<=n<=100。
接著為一個表示連接關係的n x n矩陣A。矩陣的元素是一個正整數或是字元x。A(i,j)表示由電腦i直接送一個訊息到電腦j所花的時間。若A(i,j)為x的話，表示電腦i無法把訊息直接送到電腦j。
當然，一台電腦不需要花任何時間就可以送訊息給自己，所以對任一電腦i來說，A(i,i)=0。另外，你可以假定網路是沒有方向性的（在兩電腦間傳訊息所需的花費和方向無關，都是相同的），所以對任兩台電腦i,j來說，A(i,j)=A(j,i)。
因此，題目的輸入將只會包含矩陣A的下三角形部份（不包含對角線）。也就是說，第二行的只會有一個元素A(2,1)。第三行會有兩個元素，分別是A(3,1)和A(3,2)。
輸出檔說明
對每一組測試資料，輸出從第一台電腦廣播一個訊息到其它所有電腦所需的最短傳訊時間，一組一行。
範例輸入
5
50
30 5
100 20 50
10 x x 10
4
11
x 20
2 x 13
範例輸出
35
15
二、台汽的收入問題
為了挽救日漸虧損的營運，台汽決定在花東開發一條新的路線。這條新的路線是從台北到墾丁，沿途依序編號著許多停靠站，其中台北編號為0、墾丁編號為m。
台汽打算做用一個全新的模式來改善載客量，以增加他們的收入。由於這個路線上每一車次的載客量為n名乘客，而每張車票的票價為起點和終點站之間所經過的車站數目（包括終點站）。每一列車的每一趟車次從台北出發之前，沿途的每一個車站都會確定好所有的車票訂單。如果有一份車票訂單(假設要x張車票)的起始點是S站，終點是T站的話，表示要保留恰好x張從S站到T站的車票。如果因為載客的限制，而無法接受所有的訂單的話。該公司的政策是：對於某一份訂單，採全部接受或是全部拒絕的態度。
請寫一個程式，對於每一個車次的所有訂單，找出台汽能得到最大收入的組合。對於每一張訂單來說，他們的收入是該訂單的所有乘客數乘上票價。所以，對某一車次來說，總收入即是所有接受訂單的收入總和。
輸入檔說明
輸入檔案裡面有多組測試資料。在每一組裡面的第一行包括了三個整數：列車的載客量n，墾丁站的編號m，以及車票訂單的總數p。以下的p行包含車票訂單。每張車票訂單包括三個整數：起點站、終點站、還有乘客數目。在一組測試資料中，最多會有22張車票訂單。m最大是7。
輸出檔說明
對每一組對應的測試資料，印出最大可能的總收入，一組一行。
範例輸入
10 3 4
0 2 1
1 3 5
1 2 7
題目(3)循環小數
由數學上, 我們知道, 任兩個有理數相除必定可以化為有限位數的小數或是循環小數. 在這個題目中, 請你求出任兩個正整數相除產生的循環小數的循環節.
輸入資料中每一行會給你兩個正整數 A 和 B (A, B <= 300000). 請你求出 A 除以 B 的循環節. 如果 A 除以 B 不是循環小數, 請你輸出 "not repeater". 測試資料中, 每一行的兩個數字表示一比測試數據, 0 0 表示結束. 輸出每一行表示相對的測試數據. 注意! 循環節必須從最先重覆的數字開始. 舉例來說, 1 除以 7 的循環節是 148257, 而不是 482571.
範例輸入
1 2
1 3
1 4
1 5
1 6
1 7
0 0
範例輸出
not repeater
3
not repeater
not repeater
6
142857
四、迷宮問題
走迷宮一向是深受人喜愛的遊戲, 在這個題目中題你必須找出一個三維迷宮中最短的走法
在輸入資料中, 每個迷宮的第一行有三個數字宮的長寬, 表高來有個區塊 每個區塊有行接每行有用空白隔開?表示迷宮的區塊有行, 每行有 L 個數字它p果該數字為j開表示該格子為可通行c的 表示該格子為不可通行q朽簕楖禤④丰i能有多個迷宮丰每個迷宮中間有一空白行分隔, 檔案結尾為g宮中飪鴭顙C個迷宮荌你必須輸出從座標眸滇擖X從座到衩y標1, 1, 1) 到的最短路徑 (每個迷宮一行H)輸出的格式為u?/FONT>(1,1,1)->(x,y,z)->....->(L,W,H)
如果無法走到終點, 你必須輸出滇擖X "no ro
注意! 在迷宮中你只能往上A下u左鄍k鼠eW後六個方向移動右而且不可以移出迷宮的範圍. 例如如如果你在果你在 (3, 的位置5)則你只能往置, 則你只能往 (2,4,5), (4,4,5), (3,3,5), (3,5,5), (3這六個位置移動(3假設它們沒有超過迷宮範圍而且是可通行的通?/P>
底下是一個 4×3×的迷宮
第一層
第二層
輸入的測試資料為:
4 3 2
0 1 1 0
0 0 1 0
0 1 0 0
1 0 1 0
1 1 1 1
0 0 0 0
正確答案為:
(1,1,1)->(1,2,1)->(1,3,1)->(1,3,2)->(2,3,2)->(3,3,2)->(4,3,2)
範例輸入
4 3 2
0 1 1 0
0 0 1 0
0 1 0 0
1 0 1 0
1 1 1 1
0 0 0 0
2 2 3
0 1
0 1
1 1
0 0
1 1
1 0
2 2 1
0 1
1 1
範例輸出
(1,1,1)->(1,2,1)->(1,3,1)->(1,3,2)->(2,3,2)->(3,3,2)->(4,3,2)
(1,1,1)->(1,2,1)->(1,2,2)->(2,2,2)->(2,2,3)
no route
五、最佳配對問題
有三對男女在配對活動中， 為所有參加的異性打了一個從 0 到 63 的分數。他們打的分數表格如下，縱軸（左邊）為評分者，橫軸（上面）為評分的對象：
A B C 1 2 3
1 60 35 40 A 55 40 30
2 40 45 45 B 35 50 40
3 50 55 60 C 40 40 45
從以上的表格我們可以看出 A-1, B-2, C-3 的配對會達到最高的 315 分總分。請你寫一個程式來為這樣的活動求出總分最高的最佳配對。
程式可以有多筆中間由空行隔開的輸入資料，每一筆輸入資料的第一行是一個小於 32 的非負整數 N 。如果 N=0 的話，輸入資料就到此結束，否則接下來的 2*N 行就會各有 N 個小於 64 的非負整數，代表每個人對所有異性的評分（參考輸入的問題就是以上所舉的例子）。 對除了 N=0 之外的每一筆輸入資料，你的程式必須輸出一行數字，代表在最佳配對情況下的總分。
範例輸入
3
60 35 40
40 45 45
50 55 60
55 40 30
35 50 40
40 40 45
1
3
7
0
範例輸出
315
1