Microsoft Word - Programming Contest exams 19th.doc

Size: px

Start display at page:

Download "Microsoft Word - Programming Contest exams 19th.doc"

觉习
4 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. 皇后問題 90 度旋轉不動解個數問題描述 : N 皇后問題係指在 N N 棋盤上放 N 個皇后, 使得 N 個皇后不會互相攻擊皇后的攻擊方向是四面八方, 上下左右左上右上左下右下等八個方向在八皇后的問題中, 其解答共有 92 個八皇后問題的一個解十二皇后問題的一個 90 度旋轉不動解所謂 90 度旋轉不動解意思是說, 將一個解棋盤旋轉 90 度之後還是等於自己, 沒有產生新的解對 N 皇后問題來說,90 度不動解到底有幾個呢? 輸入說明 : 輸入一正整數 N,0 < N < 100 輸出說明 : 輸出 N 皇后問題的 90 度不動解個數, 最後必須有換行字元範例 : Sample Input: Sample Output: 4 2

4 Problem 2. The heaviest branch Problem Description Given a rooted tree with positive weight associated to each node. The task is to find the maximum total weight of any subtree rooted at the child of the root. Input File Format The input contains three lines. The first line is an integers n, 1 < n which indicates the number of nodes in the tree. The second line consists of n integers which are the weights of nodes 0,1,, n-1, respectively. The total weight is no more than 100,000,000. In the third line, there are n-1 integers which are the parents of nodes 1, 2,, n-1, respectively. The root is node 0. Output Format Output the maximum total weight of any subtree rooted at the child of the root. Example Sample Input: Sample Output: 50

5 Problem 3. 貧富不均問題描述 : 快樂國貧富差距相當的大, 百姓怨聲載道, 總統為了平息民怨以及拉近貧富差距, 在與各個官員討論後決定調動稅金, 先將所有收入最高的列為 0%, 之後算出其他人年收入名次在所有人之中的百分比, 對年收入前 10% 的人課以年收入 40% 的稅金, 年收入前 11%~30% 的人課以年收入 30% 的稅金, 年收入前 31%~60% 的人課以年收入 20% 的稅金,61%~80% 的人課以 10% 的稅金, 而其餘的人不需繳稅, 以上計算出來的各個數字無條件進位到整數位, 若是有二人以上收入一樣則列在同一區間請幫快樂國政府算算, 這個政策每年可以收入多少稅金, 計算出來的錢四捨五入至整數位例如 : 有三人年收入分別為 , 為收入最高的人所以列在前 10% 的區間之中, 收入的人為 34% 所以列在 31%~60% 區間之中, 收入的人為 67% 所以列在 61%~80% 區間之中輸入說明 : 第一列為一個正整數 N( N < 100), 代表共有 N 組測試資料之後有 N 筆測試資料, 每筆測試資料佔二列, 第一列為一個正整數 M(1 M 1000), 代表共有 M 個人有收入, 第二列有 M 個正整數代表每個人的年收入, 各數之間以一個空白符號隔開輸出說明 : 每組資料輸出政府可收入的稅金, 輸出後換行共 N 組, 最後必須有換行字元範例 : Sample Input Sample Output

6 Problem 4. 分兩份問題敘述 : 將一堆錢分成兩份, 使這兩份錢的差額為最小台幣可能的面額為注意 : 原本的一堆錢是由最大的面額所組成輸入說明 : 輸入原本一堆錢的金額, 小於一百萬輸出說明 : 第一行輸出金額較高一份的組成, 依序輸出各項面額的數量, 面額順序為 [1000, 500, 100, 50, 10, 5, 1] 第二行輸出金額較少一份的組成, 依序輸出各項面額的數量, 面額順序為 [1000, 500, 100, 50, 10, 5, 1] 第三行輸出兩份金額的差額, 最後必須有換行字元範例 : Sample Input Sample Output

7 Problem 5. Recursive LCS Problem Description Write a program to compute the longest common subsequence (LCS) of two strings. A subsequence of a string s is obtained by removing some of the characters from s. For example "aed" is a subsequence of "bacedf". Therefore the longest common subsequence of "abcde" and "zzadfess" is "ade". Input File Format Input two strings. The number of character in each string is less than 100, and it doesn t include any space. (Each character is lower case.) Output Format Output the LCS result. If it doesn t contain any LCS, output none. Example Sample Input: springtime pioneer Sample Output: pine

1

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