注意事項 一 本比賽系統採用 PC 2, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界

注意事項 一 本比賽系統採用 PC 2, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界面的問題, 也就是說不用印出像是 "Please enter a number" 或 "The answer is"... 之類的文字 ; 此外, 有些題目是以讀到 EOF 為 input 結束, 有些是讀入 0 結束等等的, 必需善用 I/O 函式 上傳檔案的檔名請勿使用中文以免發生不必要的錯誤 二 比賽用的編譯器版本 :gcc 3.4.4 g++ 3.4.4 jdk 1.6.0_23 Microsoft (R) Visual C# 2010 Compiler version 4.0.30319.1 Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 若出現 Compilation Error, 可能是某些函式不支援 三 PC 2 系統判定錯誤可能原因 : 正確答案錯誤答案 多空白 假設題目 要求結尾有 換行字元 多換行字元 結尾沒有 換行字元 特別注意題目範例是否有換行字元 四 PC 2 系統判定結果說明 : 結果 說明 Yes 解題正確 No - Compilation Error 錯誤 : 編譯錯誤 No - Run-time Error 錯誤 : 程序運行錯誤 No - Time-limit Exceeded 錯誤 : 運行超時 ( 每道題都有運行時間限制 ) No - Wrong Answer 錯誤 : 運行結果與標準答案不一致 No - Excessive Output 錯誤 : 程序運行佔用內存空間超出要求 No - Output Format Error 錯誤 : 輸出格式錯誤 No - Other - Contact Staff 未知錯誤

Problem 1. Min-Heap (Time Limit: 5 seconds) 問題描述 : Heap 基本上分成兩種, 一種是 min-heap, 另一種是 max-heap, heap 最大的特色是, 任一節點恆小 / 大於子節點 由於 heap 必須符合完整二元樹的特性, 因此我們可以利用陣列來實作 heap 向上調整 向下調整 向上調整 : 以 min-heap 來說, 一個節點與其父節點做比較, 若小於父節點便與其交換, 直到 root 為止 向下調整 : 以 min-heap 來說, 與其較小的子節點比較, 如果大於較小的子節點, 即交換不斷地遞迴, 直到其小於子節點或是樹葉為止 本題利用陣列製作一最小堆積 (Min-heap) 並設計以下動作 : (a) insert(k) : 將 k 值放置於 heap 中最後一個位置, 再向上調整至適當的位置 (b) delete-min() : 刪除最小值, 在 min-heap 中最小值即為 root 的值, 刪除 root 之後, 向下調整, 若陣列為空, 則顯示 The min-heap is empty with size = 0. (c) print : 請依序印出陣列之中所有的內容 輸入說明 : 程式提供的選單如下 (a) insert(k) : 將 k 插入並印出, The min-heap is of size currentposition and the current minimum is min-num (b) delete-min() : 刪除最小值, 並印出 The min-heap is of size currentposition and the current minimum is min-num (c) print : 請依序印出陣列之中所有的內容 (d) exit 若輸入 a 10 a 3 a 8 b c, 則表示插入 10, 插入 3, 插入 8, 刪除最小值, 印 出陣列中所有的內容, 指令請以小寫字母表示, 以空白作為間隔, 指令數目 1 < n < 1000,k 值範圍介於 1 < k < 500

輸出說明 : 若輸入 a 10 a 3 a 8 b c, 則表示插入 10, 插入 3, 插入 8, 刪除最小值, 印出陣列中所有的內容 The min-heap is of size 1 and the current minimum is 10. The min-heap is of size 2 and the current minimum is 3. The min-heap is of size 3 and the current minimum is 3. The min-heap is of size 2 and the current minimum is 8. 8 10 注意執行 print 步驟以空白作為間隔, 每行要有句點, 最後必須有換行字元 範例 : Sample Input: a 8 a 19 a 4 a 90 a 3 a 2 b a 3 a 8 c d Sample Output: The min-heap is of size 1 and the current minimum is 8. The min-heap is of size 2 and the current minimum is 8. The min-heap is of size 3 and the current minimum is 4. The min-heap is of size 4 and the current minimum is 4. The min-heap is of size 5 and the current minimum is 3. The min-heap is of size 6 and the current minimum is 2. The min-heap is of size 5 and the current minimum is 3. The min-heap is of size 6 and the current minimum is 3. The min-heap is of size 7 and the current minimum is 3. 3 4 3 90 19 8 8

Problem 2. Domination in a path (Time Limit: 5 seconds) Problem Description A domination set of a graph is a node subset such that every node is either in the domination set or adjacent to a node in the set. Finding domination set of minimum total weight in general graph is an NP-hard problem. However, it can be efficiently computed by observing a recurrence relation if the input graph is a path. Input File Format The input is a path of n nodes, 1 n 90000. The weights of the nodes from left to right are given in one line. Each weight is a positive integer, 0 < w < 1000. Output Format Output the minimum weight of any domination set of this path. Example Sample Input: Sample Output: 10 20 30 40 50 50

Problem 3. 任務分配 (Time Limit: 5 seconds) 問題描述 : 任務分配, 計算最短任務所需時間 1. 一個方格代表一個任務, T1/4 : 代表 T1 任務需要 4 秒執行時間才能完成 2. 箭頭代表執行順序, 例如上圖所述 : T4 任務及 T5 任務需要等 T1 任務完成後才可進行 3. 一台處理器同一時間只能處理一個任務, 且必須做完該任務後, 才可以執行另一個任務 4. 所有的任務皆在初始化完成 例 : 假設有 3 台處理器, 處理上圖所述之任務 任務編號 所需時間 ( 秒 ) 執行順序 T1 4 無 T2 2 無 T3 2 無 T4 20 需等 T1,T2 完成才可進行 T5 20 需等 T1,T2,T3 完成才可進行 T6 11 需等 T2,T3 完成才可進行 T7 11 需等 T3 完成才可進行 請計算出如何安排, 才能在最少時間內完成所有任務呢?

輸入說明 : Process:N Task:task,time Prec:t1,t2 end N 台處理器任務, task 任務名稱, time 任務執行時間優先權, t1 必須在 t2 前執行, 也就是說 t2 必須等到 t1 結束才可以開始執行輸入結束符號程式開始執行 0 < N < 100,task 總數不超過 5000, 以小寫字母表示, 例如 : t1,t2, 各任務 執行時間介於 0 < time < 500 輸出說明 : 輸出所有任務所需最短執行時間, 最後必須有換行字元 範例 : Sample Input Process:3 Task:t1,4 Task:t2,2 Task:t3,2 Task:t4,20 Task:t5,20 Task:t6,11 Task:t7,11 Prec:t1,t4 Prec:t2,t4 Prec:t2,t5 Prec:t2,t6 Prec:t3,t5 Prec:t3,t6 Prec:t3,t7 end Sample Output 24

Problem 4. 網路多重最短路徑 (Time Limit: 5 seconds) 問題敘述 : 在圖 ( 網路 ) 中 最短路徑 的定義為網路中連接起始節點至目標節點的所有路徑中具有最小的 路徑權重值 網路中的路徑權重值是構成此路徑的所有 連線權重值 的總和 使用鄰接矩陣表示的網路其每一條連線的權重值都假設為 1 給予一代表無向連通圖的鄰接矩陣並指定起始節點與目標節點, 請計算出連接起始節點至目標節點的所有 ( 大於或等於 1) 最短路徑 輸入說明 : 輸入分為兩部份, 第一部份只有一行, 此行中有三個用逗號分隔開的介於 1 到 99 的數字, 第一個數字代表要計算的圖中節點數目 第二個數字與第三個 數字分別表示起始節點與目標節點 第二部份是鄰接矩陣, 總共列數剛好有節點個列, 每一列中有節點個由空隔分開的 0 或 1 第 i 列中的第 j 個 0 或 1 代表由節點 i 到節點 j 的連線是否存在 (0 表示不存在,1 表示存在 ) 沒有自我迴圈連線表示第 i 列中的第 i 個元素值為 0 連線沒有方向性, 因此鄰接矩陣為對稱矩陣 輸出說明 : 每一條最短路徑用一行表示, 列出由起始節點至目標節點的路徑中所經過的 節點編號 ( 包括起始節點與目標節點 ), 節點與節點間用逗號分隔開 若超過一組的最短路徑請依數字大小順序換行輸出, 最後必須有換行字元

範例 : Sample Input 9,1,5 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 Sample Output 1,2,5 1,4,5

Problem 5. Maximum Sub-sequence Product (Time Limit: 5 seconds) Problem Description Bob needs money, and since he knows you are here, he decided to gamble intelligently. The game is rather simple: each player gets a sequence of integers. The players must determine, by using their mega-pocket computers, which is the maximum product value which can be computed with non empty sub-sequences of consecutive numbers from the given sequence. The winner is the one which gets first the right result. Can you help Bob with a program to compute quickly the wanted product, particularly when the sequence is quite long? Input File Format The input file contains sequences of numbers. Each number will have at most 5 digits. There will be at most 100 numbers in each sequence. Each sequence starts on a new line and may continue on several subsequent lines. Each sequence ends with the number -999999 (which is not part of the sequence). No more than 10 sequences. Output Format The maximum sub-sequence product for each sequence must be written on the standard output, on a different line. A simple example is illustrated in the sample below. Example Sample Input: 1 2 3-999999 -5-2 2-30 -999999-8 -999999-1 0-2 -999999 Sample Output: 6 120-8 0