015/06/10 第三十九次 ITSA 線上程式設計競賽 競賽試題 共 5 題,8 頁 1
注意事項 一 本比賽系統採用 PC, 所使用的 I/O 是標準輸出輸入裝置, 所以可以使用 C 語言的 scanf ( ) printf ( ), 或是 C++ 語言上的 cin cout 來讀入及輸出資料, 比較要注意的是 : 本系統並不是用人工方式來 keyin 資料, 所以不必在意使用者界面的問題, 也就是說不用印出像是 "Please enter a number" 或 "The answer is"... 之類的文字 ; 此外, 有些題目是以讀到 EOF 為 input 結束, 有些是讀入 0 結束等等的, 必需善用 I/O 函式 上傳檔案的檔名請勿使用中文以免發生不必要的錯誤 二 比賽用的編譯器版本 : C/C++: gcc:4.9. (Cygwin 1.7.5_1) g++:4.9. (Cygwin 1.7.5_1) Java: Version 1.8.0_45 Java(TM) SE Runtime Environment (build 1.8.0_45-b14) Java HotSpot(TM) 64-Bit Server VM(build 5.45-b0, mixed mode) Microsoft C#: Microsoft (R) Visual C# Compiler version 4.0.019.409 Microsoft C++: Microsoft (R) -bit C/C++ Optimizing Compiler Version 16.00.019.01 Compiler Command line: C:gcc -O -std=gnu99 -static $* -lm C++:g++ -O -std=gnu++0x -static $* C++11:g++ -O -std=c++11 -static $* C#:csc Microsoft C++:cl Java:javac For Java, the compiled code will be executed using the following command: java -Xmx104m -Xss8m " 本次比賽提供兩種 C++ 選擇, 上傳時請留意語言選項 " 若出現 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 未知錯誤
Problem 1. X+1 數列產生 問題描述 : 有一個很有趣的數列問題, 它的英文的名字叫 Collatz 猜想 這種數列的第一項由使用者自行給予, 而最後一項一定是 1, 它的規則如下 : 如果這個數是偶數, 你就取它的一半, 如果是奇數, 你就把它三倍再加一,, 如此重覆下去, 直到 1 為止 請寫下一條程式, 當我給予它一個數字, 則以該數字做為起始值完成此數列 輸入說明 : 輸入一開始是一個整數 n, 代表共有 n 筆測試資料 之後有 n 行, 每行為一個整數 輸出說明 : 範例 : n 個數列, 每行一個數字 8 10 5 16 8 4 1 8 4 1 4
Problem. 矩陣分素乘積 問題描述 : 寫一個程式輸入兩個相同維度的矩陣, 求得兩矩陣的分素乘積 ( entrywise product ) 兩個 m*n 矩陣 A 與 B 的分素乘積 A B, 定義為 例如, (A B)ij = aij bij 輸入說明 : 一開始是一個整數 x, 代表共有 x 筆測試資料 每個測資的第一行輸入矩陣的維度 m ( row number, 列數 ) 與 n ( column number, 行數 ), 中間用單一空白區隔, m 與 n 均為大於 0 小於 10 的正整數 接著開始逐行輸入兩個矩陣的內容, 每一行代表矩陣一列 ( row ) 的數值, 數值間用單一空白區隔, 每個數值可為任意正負整數 輸出說明 : 每個測資輸出兩個矩陣的分素乘積內容, 以一行輸出一列 ( row ) 的方式呈現 數值間用單一空白區隔, 最後必須有換行字元 範例 : 1 1 5 0 4 1 7 8 5 0 5
Problem. 爬樓梯 問題描述 : 一至二樓有 n 級樓梯, 某人上樓, 每次可跨 1 級或 級, 不同上樓的方 法有幾種? 輸入說明 : 一開始是一個整數 x, 代表共有 x 筆測試資料 之後有 x 行, 每行輸入樓梯之級數 n ( n 0) 輸出說明 : 範例 : 每個測資以一行輸出不同上樓的方法總數 1 77 6
Problem 4. 文字接龍 問題描述 : 小義對撲克牌中的接龍遊戲非常著迷, 不管多麻煩的牌型, 他總能將整副牌排出來 為此, 小義常常洋洋得意地說自己是接龍高手, 聲稱所有跟接龍有關的遊戲他都很在行, 沒有甚麼難得倒他 他的哥哥小嘉對他的自滿很不以為是, 決定用英文字母接龍來考考他 為了殺殺他的銳氣, 小嘉給了幾個規則 : 首先給一個字串, 每個字母由左而右處理, 當遇到字母 a 時, 必須將其後的所有的字母順序反轉 ; 遇到字母 b 時, 則須將其後所有字母複製一遍接在原字串後面 ; 當遇到字母 c 時, 要將其後的兩個字母從字串中刪除 ; 若遇到其他字母則不做任何處理 例如, 原始字串為 acebf, 則次字串的變化為 : acebf afbec(a 以後的反轉 ) afbecec(b 以後的複製 ) afbec(c 以後兩個刪除 ) 依此規則讓小義將最後的字串找出來 輸入說明 : 輸入一開始是一個整數 n, 代表共有 n 筆測試資料 之後有 n 行, 每行有一個長 度大於 1 且小於等於 500 的字串 每個字串在處理過程中長度都不會超過 1000 字串中的字元僅包含小寫英文字母 輸出說明 : 每筆測試結果輸出於一行 範例 : 5 about peter fractional acebf aliceisnotaboy atuob peter fralacon afbec ayobalicsnotatonsiec 7
Problem 5. Cable Car Assignment Problem Description In the line of people who waiting for taking the cable car, there are many groups of people who knows each other. The staff will pick up the combination which is the most suitable for the number of people a cable car can be taken. However, if the group picked is behind a number of groups, these groups will feel not good. How does the staff pick up groups will make complains less? Suppose a cable car can take 6 people. If there are n groups of people not be picked before the picked one, then there will be n complain value. Please write a program to find the combination with smallest n from the 6 groups inputted by user. Input Format The input consists of a number of test cases. The first line of the input file contains an integer indicating the number of test cases to follow. Each test case consists of 6 positive integers. Two integers are separated by a, and space. Output Format For each test case, output the best combination and the complaint value in one line, as shown in the sample output. Example 1, 5,,, 4, 6 4,,, 5, 6, 5, 5, 4,, 1, The best combination is 1, 5, Complaint=0 The best combination is,, Complaint=1 The best combination is 4,, Complaint= 8