《数据结构组-2014年东华大学acm校内友谊赛》由会员分享，可在线阅读，更多相关《数据结构组-2014年东华大学acm校内友谊赛（20页珍藏版）》请在金锄头文库上搜索。
1、2014 年东华大学年东华大学 ACM校内友谊赛校内友谊赛 （数据结构组）（数据结构组） 2014.12.16 12:3017:30 试试 题题 册册 1 2014 年东华大学 ACM 校内友谊赛 Agimadei Time Limit: 5 sec Description In the universe, there lives one kind of human called Agi. One of their features is black, yes , the same as Teacher Zeng. They chat with each other by saying som
2、ething like “Agimadei“. They have N groups, each has a planet shapes like sphere. And the planets are far from each other. There is a king of Agi named “Gaojibin“, now because of the huge cost of traveling between planets and planets, he wants to build some super roads between them. He can only buil
3、d roads from the surface of one planet to the surface of the other planet. Now he wants to minimize the total cost of the road to be built between these N groups. You must know that the planet would be overlapped or intersect, in the case, you neednt calculate the cost. You can assume that the probl
4、em always has answer. If you cant solve this problem, “Gaojibin“ would say “Agimadei“. 2 2014 年东华大学 ACM 校内友谊赛 The Input There are multiple test cases; The first line contains an integer N (N:1,1000), N is the number of groups. Then follows N lines, each line contains four integer x, y, z, r. The cen
5、tre of sphere is (x, y, z), and the radius is r. Each of x, y, z and r is positive and is no larger than 10000. The Output Output the minimal total cost. You should output exactly 6 digits after the decimal point. Sample Input 3 10 10 50 10 40 10 50 10 40 40 50 10 2 30 30 30 20 40 40 40 20 Sample Ou
6、tput 20.000000 0.000000 Author: zy 3 2014 年东华大学 ACM 校内友谊赛 Can their ideals come true? Time Limit: 2 sec Description On the Donghua planet, almost every grade 3 student of senior high school has ideals of entering prestigious universities. There are M universities on the planet and each university ca
7、n only accept a limited number of freshmen. So it is challenging for the N students to apply for universities, and it is also complicated for the government to manage the enrollment. In order to keep the enrollment fair and create more opportunities for students, the government has formulated such a
8、 scheme. Every student can take a series of exams, appraisals, interviews and eventually get a composite score by the impartial, authoritative third party. The score is universal for every university. Then they can apply for their ideal universities. To ensure the quality of students, every universi
9、ty will set a threshold score. That means if the students score is lower than the threshold, his or her application is invalid. The enrollment management department will do an overall consideration of all valid applications. In order to make full use of resources, a student qualified for many applie
10、d universities will be arranged to one of them. No matter which university the student was arranged to, he or she will feel happy. Higher education is vital for everyone, so the President wants to keep the rate of enrollment as high as possible. Can you tell him the number of students whose ideals c
11、an not come true by this enrollment management strategy. The Input There are multiple test cases. Each test case will be formatted according to the following description: The 1st line: contains two integers N (1 X*X . function s(x) determines the sum of all digits in the decimal representation of nu
12、mber x. For example,when x=123456, s(x)=1+2+3+4+5+6=21. The Input There will be several test cases(no more than 110), for each test case , there will be one line contains three space-separated integers: a, b, c (1 a 5; 1 b 10000; - 10000 c 10000). The Output For each case, output the positive intege
13、r Y in a line. Pay attention: If X do not exist, output “Agimadei” instead . Sample Input 1 2 -18 2 2 -1 Sample Output Agimadei 967 Author: toyking 12 2014 年东华大学 ACM 校内友谊赛 Math Kingdom Time Limit: 2 sec Description Bob lives in Math Kingdom, there are N cities (numbered from 1 to N) and M roads in t
14、he kingdom. Each city has special cars which can take people from the city to any cities connected with it in exact ti hours, no matter how far or near they are. At the same time, every city has a Clock Number Ti. Now, we define function f(x), its value is the number of prime factors of x. Coinciden
15、tally, ti equals to f(Ti). For example, if there is a bidirectional road from u to v, us Clock Number is 20, vs Clock Number is 30, as we know that 20 = 2*2*5, 30 = 2*3*5, 2 and 5 are prime factors of 20, 2、3 and 5 are prime factors of 30, so f(20) = 2 and it costs 2 hours if Bob wants to go from u
16、to v, f(30) = 3 and it costs 3 hours from v to u. Desert to “Math Kingdom”, isnt it? Here is the graph of the second sample input test case: Bob wants to know the minimum time cost from city u to city v? The Input The first line contains an integer T (T = 11), denoting the number of the test cases. For each test case, the first line contains, N (2 = N = 100) and M (N-1 = M = (N-1)*N/2), as mentioned above. The second line contains N integers, representing the clock number Ti
