四川理工学院2012年ACM程序设计赛试题.doc

2012年四川理工学院“达内杯”大学生程序设计竞赛Problem 1：Sorting There are 16 random sorting numbers from 0 to 15, and they could be converted to different binary numbers, which have 4 digits. Please code algorithm to sort them by the order that the first there digits of the former number is same to the last there digits of the following. The first number of the sorted is always the first given number. Sample Input： 1 3 5 7 9 11 13 15 0 2 4 6 8 10 12 14 Sample Output： 1 2 4 9 3 7 15 14 13 10 5 11 6 12 8 0 Problem 2：Solution of Equation In the interval [0,1], please programming to give the real root, of which error is less than 10-3, of equation ax3+bx2+cx+d=0, where a, b ,c and d are real number. And print the real root or the character “no solution”. Sample Input： 1：a =1 b =－1 c =－2 d =1 2：a =1 b =1 c =1 d =1 Sample Output： 1：x =0.444335937 2：no solution Problem 3：The Triangle Description 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1 Number Triangle) Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. Input Your program is to read from standard input. The first line contains one integer n: the number of rows in the triangle. The following n lines describe the data of the triangle. The number of rows in the triangle is = 1 but = 100. The numbers in the triangle, all integers, are between 0 and 99. Output Your program is to write to standard output. The highest sum is written as an integer. Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 Problem 4：Common Subsequence Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = {x1, x2, ..., xm }, another sequence Z = { z1, z2, ..., zk } is a subsequence of X if there exists a strictly increasing se