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

Size: px

Start display at page:

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

顶吕
5 years ago
Views:

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

2 注意事項一本比賽系統採用 PC 2, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界面的問題, 也就是說不用印出像是 "Please enter a number" 或 "The answer is"... 之類的文字 ; 此外, 有些題目是以讀到 EOF 為 input 結束, 有些是讀入 0 結束等等的, 必需善用 I/O 函式上傳檔案的檔名請勿使用中文以免發生不必要的錯誤二比賽用的編譯器版本 :gcc g jdk 1.6.0_23 Microsoft (R) Visual C# 2010 Compiler version Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 若出現 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 未知錯誤

3 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

4 輸出說明 : 若輸入 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 注意執行 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

5 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 The weights of the nodes from left to right are given in one line. Each weight is a positive integer, 0 < w < Output Format Output the minimum weight of any domination set of this path. Example Sample Input: Sample Output:

6 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 完成才可進行請計算出如何安排, 才能在最少時間內完成所有任務呢?

7 輸入說明 : 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

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

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

10 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 (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: Sample Output:

1

1 注意事項一本比賽系統採用 PC, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界面的問題, 也就是說不用印出像是 "Please enter a number" 或 "The answer