2009靜宜大學程式設計競賽考題 - 靜宜大學資訊學院.doc

2009靜宜大學程式設計競賽 競賽日期：97.06.04 考試時間：15:00-18:00 注意事項：1.採即時評分，每題送出答案後，將立即告知對或錯。答錯的題目修改後可重新送審。 2.每送一次錯誤解答，該題的解題時間將被多加 20 分鐘。3.參賽者可攜帶書籍、手冊、紙本式的程式碼。但不可攜帶機器可讀寫的任何軟體資料，亦不可攜帶自己的電腦、終端機、計算機或電子字典，並嚴禁使用行動電話及呼叫器，以免干擾其他隊伍。4.程式說明：共八題程式，其中第五題的程式需設計從鍵盤輸入Input資料，其餘的題目需設計從指定的檔案讀入Input資料。每題的Input有說明輸入檔案資料的格式，每題的Sample Input為輸入檔案內容的舉例。第一題解多項式：設有一個m-1多項式F(X) = am-1Xm-1+ am-2Xm-2+ am-2Xm-2+ a1X1+ a0，若已知在F(X)上任意m點坐標 (X1，Y1)、(X2，Y2) 、(Xm，Ym)。寫一程式根據所給的點，計算出多項式F(0)的值。Input你的程式將讀入一個輸入檔，檔名為“LagPolynomial.in”. 此檔包含一個或多個測試實例，每一個測試實例包含m的點，寫在同一筆記錄上(record)上，用來計算出一個m-1多項式，其中同一筆記錄的每兩個整數值(integer)為多項式的一點。例如實例一，1 4 2 5 3 6，分別表示在一個2次多項式的3個已知點的坐標 (1, 4)、(2,5)、(3, 6)。Output對於每一筆記錄的測試實例，你的程式將印出當多項式F(0)的值在標準輸出上(螢幕)。印出的來的多項式值分別給於順序編號，如F1(0)，F2(0)，Fn(0)，分別對應到n筆的測試實例。例如實例一，為一個2次多項式，其F(0)所的輸出的值為7，表達成F1(0)=7。Sample input 1 4 2 5 3 10 -1 -3 1 5 2 0 4 2 Sample Output F1(0) = 7F2(0) = 6第二題Chinese Remainder Theorem： Please write a program which takes multiple modulo equations (x = a mod b), and returns the smallest solution to the equations. InputYour program will read the input file “ChinaRemainder.in”. The file includes only one test case with multiple module equations. OutputFor each test case, your program will print the smallest solution following with the equal expression of the variable (for example, “x =”) on the StdOut (Monitor). Sample input x = 4 mod 5x = 7 mod 8x = 3 mod 9Sample Output x = 39第三題Subset Sum Problem：Given a set of integers, l1, ln (positive integers) and a bound B (non-negative integer), please write a program to decide whether there is a subset belonging to the set such that their total sum equals B. InputYou program will read the input file “SumProblem.in”. The file includes one or more test case. Each test case includes a record, B and a set of integers.OutputFor each record, your program will print “YES” or “NO” to the StdOut (Monitor). If “YES” is the answer, please also print the subset following with “YES” Sample Input0 7 3 2 5 817 2 5 9 21Sample OutputYES 3 2 5NO第四題Common Permutation：An input file, named as “Permutation.in”, contains several lines of input. Consecutive two lines make a pair of input. That means in the input file String1 and String2 is a pair of input, String3 and String4 is a pair of input and so on. Each line contains one string. Each string is on a separate line and consists of at most 1000 lowercase letters. Given multiple strings of lowercase letters, String1, String2, , and StringN, in the file. For example, the first line of a pair contains String1 and the second contains String2. Print the longest string str of lowercase letters such that there is a permutation of str that is a subsequence of String1 and there is a permutation of str that is a subsequence of String2. InputYour program will read the input file “Permutation.in”. The file includes one or more test case (from String1 to StringN, N is a positive even number). OutputFor each pair of input, your program will print a line containing str to the StdOut (Monitor). If several str satisfy the criteria above, choose the first one in alphabetical order. Sample InputprettywomenwalkingdownthestreetSample Outputenwet第五題 第 13 頁，共 13 頁Bit-Reversal program：Bit-reversal is important data reordering operations in the Fast Fourier Transform (FFT). Standard Bit-reversal algorithm is described as the following: for i = 0 to n-1 Yi = Xreverseiwhere n is the size of both array X and Y. Suppose n is always powers of two (2p) where p is number of bits. For example, n=8 or 23, p=3, so the number of bits is 3. i in decimali base 2Reverse of i base 2Reverse of i base 100000000010011004201001023011110641000011510110156110011371111117 Input:Using standard input (input from keyboard)N where N is 2P. for example, 2, 4, 8,16,32,64,128,etc. Output:(i and the reverse of i) where i from 0 to N-1Sample input: 8Sample output: 0 - 0 1 4 2 2 3 6 4 1 5 5 6 3 7 7 第六題I know numbers：You are requested to write a program to recognize integers and real numbers. For example, 3, 46, 20, 40, 003, 3E2 or 3E+2 (This is 3*102) are integers. And, 3.45, .89, 0.23, 2.3E-2 (2.3*10-2) are real numbers, and let considered 23E-4 (23*10-4) is a real number.Input:Read the input file: Numbers.inKN1 N2 NKFirst line of input K is the number of input data that we need to read from the next line.Ouput:N1 is either integer or real numberN2 is either integer or real number NK is either integer or real numberSample input:4 03 3E2 1223E-5 0.23Sample output:03 is integer 3E2 is integer1223E-5 is real number0.23 is real number第七題 Confederations (聯邦城市)：There are wars in this country now and you must to travel all cities all over the country, but each city is only visited once.Confederations identified by colors were formed among the cities all over the country, and each city belongs to at least one and at most two confederations. When trying to enter a city, you must give to the border officer a ticket from one of the confederations this city belongs to. When leaving the city, you receive a ticket from the other color confederation ticket the city belongs to (when the city belongs to two confederations), but you will receive the same color confederation ticket if the city only belongs to one confederation. You must obey the confederations rules, and visit all cities, and visit each city exactly once.For example, suppose there are four cities, labeled from 0 to 3. City 0 belongs to confederations red and green; city 1 belongs only to red; city 2 belongs to green and yellow; and city 3 belongs to blue and red. If you choose to start at city 0, you can enter it carrying either the red or the green ticket and leave receiving other. Should you choose the red ticket, you will leave with a green ticket, and then there is only city 2 you can travel to. When leaving city 2, you receive the yellow ticket and now you cannot go anywhere else. If you had chosen the green ticket as the first you would receive the red one when leaving, and then you could travel to cities 1 or 3. If you choose city 3, when leaving you will receive the blue ticket and again you cannot go anywhere else. If you choose city 1, you receive the red ticket again when leaving city 1 belongs only to the red confederation and can only travel to city 3 and will never get to city 2. Thus, it is not possible to visit each city exactly once starting at city 0. It is possible, however, starting at city 2 with the yellow ticket, leaving the city with the green ticket, then visiting city 0, leaving with red ticket, then visiting city 1, leaving with red ticket again and, at last, visiting city 3.Input:Read the input file: Confederation.inThe input contains several test cases. The first line of a test case contains two integers N and C, separated by one space, indicating respectively the number of cities (1 = N = 500) and confederations (1 = C =100) in the country. Each of the next C lines describes a confederation. It starts with one integer K (0= K= N) and then K integers representing the cities which belong to this confederation. All integers are separated by single spaces and cities are numbered from 0 to N 1. Each city will appear at least once and at most twice and no city will be repeated on the same confederation. The end of input is indicated by a line containing two zeroes separated by a single space.Output:For each test case in the input, your program must print a single line, containing the integer -1 if its not possible to match the requirements or one integer representing the city where you can start his journey. If there are multiple correct answers, print the smallest one.Sample Input:4 41 33 0 1 32 0 21 23 41 03 0 1 21 11 23 41 12 1 02 0 21 20 0Sample output:2-11第八題 Can you add this?：Given two integers, calculate and output their sum. There are three types of integers: Hex (Hexa), Oct (Octal), and Dec (Decimal) integer number.Input:Using the input file: Addnum.inHex n1 n2 Oct n1 n2Dec n1 n2Output:Always in decimal integer numberSample input:Hex 0f 01Dec 100 200Oct 342 237Sample output:16300385參考資料 A. Illustrations of I/O programs with C, C+, and Java languages1. T