1

Size: px

Start display at page:

Download "1"

脂富
4 years ago
Views:

1 1

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

2 注意事項一本比賽系統採用 PC, 所使用的 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_3 Microsoft (R) Visual C# 010 Compiler version Microsoft (R) 3-bit C/C++ Optimizing Compiler Version 若出現 Compilation Error, 可能是某些函式不支援三 PC 系統判定錯誤可能原因 : 正確答案錯誤答案多空白假設題目要求結尾有換行字元多換行字元結尾沒有換行字元特別注意題目範例是否有換行字元四 PC 系統判定結果說明 : 結果說明 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. 沙漠綠洲問題描述 : 在沙漠中有一個村落, 村落旁邊有一個綠洲, 村民所有的水都要從綠洲取得, 村長發給每一戶人家一個水桶, 以及家中每個人一個水瓢, 年齡愈大的人拿到的水瓢容積愈大, 並且規定每戶人家每天只能只能裝一桶水, 取水時必須排隊, 每個人一次只能舀一瓢水, 而且水瓢必須裝滿, 但每人不限制只舀水一次今天小明全家出動, 要去裝水, 知道水桶可裝 M 公升的水, 請幫小明算算全家人如何在排最少舀水幾次能將水桶裝滿, 而綠洲的水相當珍貴, 所以不能讓水滿出水桶輸入說明 : 第一行有一個正整數 N (1 N 10), 表示共有 N 筆測試資料, 之後有 N 行, 每行為一筆測試資料每筆測資第一個數為一個正整數 K (1 K 100), 代表家中人口數 ( 即水瓢的數量 ), 之後有 K +1 個正整數, 前面 K 個數字分別代表各水瓢的容積, 最後一個則代表水桶的容積 (M 10000), 每個整數間均有一個空格隔開輸出說明 : 每筆測試資料輸出最少舀水次數於一行, 若無法在不溢出的情況下將水桶裝滿則輸出 0, 最後必須有換行字元範例 :

4 Problem. Matching Points in the Plane Problem Description Consider n points on the XY-plane. Let S be the set of n points on the X-axis and T the set of n points on the Y-axis. For s S and t T, we define their Euclidean distance d(s, t) is the length of the line segment st. Our goal is to find a 1-to-1 mapping between S and T such that the total Euclidean distance is maximum. That is, we want to find a 1-to-1 function f : {1..n} {1..n} such that n i 1 d( s i, t f ( i) ) is maximized, in which S = {s i 1 i n} and T = {t i 1 i n}. Technical Specifications 1. All coordinates are 16-bits integers. (positive & negative integers, including 0). n is a positive integer Input File Format The first line contains an integer ( i < 100 ) indicating the number of test cases to follow. Each test case has two lines: the first line for the X-coordinates of the points in S and the second line for the Y-coordinates of the points in T. There is a space between any two integers. Output Format For each test case, output the integer part of the maximum total distance in a line. 4

5 Example

6 Problem 3. The Numbers 問題描述 : 請寫一個程式, 判斷一個數字 N 出現在另外一個數字 M 中的次數 10 N 99, M 輸入說明 : 輸入測資個數 n < 100 每筆資料有兩個整數,N 和 M 輸出說明 : 每筆測資輸出一整數, 也就是 N 出現在 M 裡面的次數, 最後必須有換行字元範例 :

7 問題描述 : Problem 4. 列印包含特定元素的子集合請利用一維整數陣列儲存一個集合 S, S 含有 N 個元素, 元素分別為 1~N 的整數請撰寫一個程式, 產生集合 S 的所有子集合 P, 假設 P 不含空集合與 S 本身, 請將 P 存入一個二維整數陣列中, 並將 P 中含有元素 1 與 N 的子集合列印出來例如 : 假設集合 S = {1,, 3}, S 的子集合 P = {{1}, {}, {3}, {1,}, {1,3}, {,3}}, 則包含元素 1 與 3 的子集合為 {1}, {3}, {1,}, {1,3}, {,3}} 輸入說明 : 輸入一個整數 N ( N < ), 則此集合的元素為 {1,,.., N} 輸出說明 : 分別列出包含元素 1 與 N 的子集合, 集合與集合以換行區隔, 集合內的元素以逗點做區隔, 須依照數字大小順序輸出, 最後必須有換行字元範例 : , 1,3 1,4,4 3,4 1,,3 1,,4 1,3,4,3,4 7

8 Problem 5. Maximum Consecutive Sum Problem Description There is an integer array. We want to find a consecutive subsequence in it, which have the maximal sum in all subsequences. For example, an array like this: -1, 5, 7, -, 8, -, 1, -5, -8, 4, 6, -, the consecutive subsequence sum have (-1) + 5 = 4, (-1) (-) + 8 = 17, = 1, etc. And the Maximum consecutive sum in this array is (-) + 8 = 18 Technical Specification 1. Solve this problem in time complexity O(n 3 ).. The input array has elements less than The worst case of output is 0. ( output will bigger than 0. ) Input Format A string contains integers ( -10 < i < 10 ) with space to separate. Output Format An integer which is the answer of the given. Example

Microsoft Word - Programming Contest exams 19th.doc

Microsoft Word - Programming Contest exams 19th.doc 注意事項一本比賽系統採用 PC 2, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界面的問題, 也就是說不用印出像是 "Please enter a number" 或 "The answer