內容
一個程式的執行路徑關係，可以描繪成一個流程圖形(flow graph)，例如左
下副程序 (subroutine) fpath(x,y,z) 從第1 行到第24 行（每一行指令左邊的
數字代表行號，行號為正整數 n，如圖所示），流程關係依照 if 與 while 的條
件真假，會執行不同的路徑。
例如第 3 行，若 if 條件為真(true)，則執行路徑為 3 4 5，若條件不成立(false)，
則執行路徑為 3 5。依此，可畫出對應之流程關係圖如上。觀察上述副程序
fpath(x,y,z)，其流程關係，根據傳入參數 x, y, z 數值（假設都是32bits 的非負
整數）的不同，會有不同的執行路徑。
以圖形 (graph)的路徑 (path) 觀點，從端點 1 為起點到終點 24，可以有不
同路徑，例如路徑 1 2 3 5 6 12 13 16 17 23 24 為一種走法，我們稱為可行路徑
(feasible path)，而1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24 也是一種走法，但因為任
何零或正整數 x, y, z 的傳入參數值都無法循此路徑執行，我們稱為不可行路徑
(infeasible path)。針對上述程式範例，根據其流程關係所形成之圖形，給予任一
由起點到終點的路徑，判斷路徑是否可行。若可行，請找出一組滿足此路徑之
x, y, z，令 x + y + z 最小(其中 x,y,z 都必須大於或等於 0)，並輸出。 輸入參數
x, y, z 皆為合法之 32 bits 正整數或零，測試資料中不含令運算產生 overflow 與
underflow 之情況。
輸入說明
第一行為資料筆數 N (0<N<=100)。接續 N行為路徑輸入描述，以序列的行
號表示，行號間以一個或以上的空白隔開，每一行為一個路徑描述，起點為1、
終點為24，最多包含 1000 個行號路徑（行號 L 範圍為整數 0<L<25），例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
號表示，行號間以一個或以上的空白隔開，每一行為一個路徑描述，起點為1、
終點為24，最多包含 1000 個行號路徑（行號 L 範圍為整數 0<L<25），例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
輸出說明
根據上述範例程式所形成之圖形，依序判斷所給定之路徑，在「限定x, y, z
都是大於或等於零」的情況下，是否可行。若為可行路徑，輸出 min (x +y +z) 之
數值，例如min (x +y + z) = 5，則輸出
5
否則輸出：
inf
每筆路徑判定結果只以逗點相隔，每行最多輸出15 筆結果（每行最後一筆資料
無逗點與空白），超出則換行。請依照範例格式輸出。
都是大於或等於零」的情況下，是否可行。若為可行路徑，輸出 min (x +y +z) 之
數值，例如min (x +y + z) = 5，則輸出
5
否則輸出：
inf
每筆路徑判定結果只以逗點相隔，每行最多輸出15 筆結果（每行最後一筆資料
無逗點與空白），超出則換行。請依照範例格式輸出。
範例輸入
#1
輸入範例 1： 3 1 2 3 5 6 12 13 16 17 23 24 1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 輸入範例 2: 18 1 2 3 5 6 12 13 16 17 23 24 17 1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 22 23 17 18 19 22 23 24
範例輸出
#1
輸出範例1： 0,inf,inf 輸出範例2： 0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 ：
感谢morris1028提供图片！
標籤:
出處:
98學年度全國資訊學科能力競賽
[管理者：
swda289346
(太威啦)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||