ACM第3周周赛试题.doc

A：Max Sum of Max-K-sub-sequence（3415）Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) 本套试题摘自杭电：/vip/contest_show.php?cid=291Total Submission(s): 525Accepted Submission(s): 51Problem DescriptionGiven a circle sequence A1,A2,A3.An. Circle sequence means the left neighbour of A1 is An , and the right neighbour of An is A1.Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.InputThe first line of the input contains an integer T(1=T=100) which means the number of test cases. Then T lines follow, each line starts with two integers N , K(1=N=100000 , 1=K=N), then N integers followed(all the integers are between -1000 and 1000). OutputFor each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them.Sample Input46 36 -1 2 -6 5 -56 46 -1 2 -6 5 -56 3-1 2 -6 5 -5 66 6-1 -1 -1 -1 -1 -1Sample Output7 1 37 1 37 6 2-1 1 1B：Marriage Match IVTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 295Accepted Submission(s): 38Problem DescriptionDo not sincere non-interference。Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, its said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once. So, under a good RP, starvae may have many chances to get to city B. But he dont know how many chances at most he can make a data with the girl he likes . Could you help starvae?InputThe first line is an integer T indicating the case number.(1=T=65)For each case,there are two integer n and m in the first line ( 2=n=1000, 0=m=100000 ) ,n is the number of the city and m is the number of the roads.Then follows m line ,each line have three integers a,b,c,(1=a,b=n,0c=1000)it means there is a road from a to b and its distance is c, while there may have no road from b to a. There may have a road from a to a,but you can ignore it. If there are two roads from a to b, they are different.At last is a line with two integer A and B(1=A,B=N,A!=B), means the number of city A and city B.There may be some blank line between each case.OutputOutput a line with a integer, means the chances starvae can get at most.Sample Input37 81 2 11 3 12 4 13 4 14 5 14 6 15 7 16 7 11 76 71 2 12 3 11 3 33 4 13 5 14 6 15 6 11 62 21 2 11 2 21 2Sample Output211C：The lastest Math theory problemTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 57Accepted Submission(s): 7Problem DescriptionThere is a positive integer N,satisfied that (N / a1) equals K1a1, (N / a2) equals K2a2 and so on. Then, I want you to tell me the smallest N.InputInput is a integer n(1=n=6), then n numbers ai (16 ai 10000 )described above.OutputIf there exists such a N,output N mod 19880502, else -1 instead. Sample Input1323217 19Sample Output3233493625D：Beautiful DreamTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 200Accepted Submission(s): 22Problem DescriptionWhen we were a child, we all had a beautiful dream, time flies, where is your colorful dream living in now?Get it? If not, it doesnt matter, today is your lucky day, our kindly angel cast some items, if you get more than m different kind of items, you will get the gift of the angel: help you achieve your childhood dream.Now we know the number of each item, find the maximum number of people who can achieve their dreams.InputThere are several test cases in the input.The first line of each case contains two integer n (0 n = 100) and m (0 m = 0 & a + b + c = 9) Meaning of a, b, and c are described in the problem statement. The last case contains exactly three 0s for all of a, b, c and indicates the end of input stream. This line should not be processed.OutputYour program should print a single integer for each input in a single line. The integer will state that how many solution there are for the given size of a, b and c.Sample Input2 3 41 1 10 0 0Sample Output74Note:The valid solutions for the second sample input-output are as following:2*3 =62*4 =83*2 =64*2 =8F：Bus FairTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 978Accepted Submission(s): 291Problem DescriptionYou are now in Foolish Land. Once moving in Foolish Land you found that there is a strange Bus fair system. The fair of moving one kilometer by bus in that country is one coin. If you want to go to X km and your friend wants to go to Y km then you can buy a ticket of X+Y coins (you are also allowed to buy two or more tickets for you two).Now as a programmer, you want to show your creativity in buying tickets! Suppose, your friend wants to go 1 km and you want to go 2 km. Then its enough for you to buy a 2coin ticket! Because both of you are valid passengers before crossing the first km. and when your bus cross the first km your friend gets down from the bus. So you have the ticket of 2km! And you can safely reach to your destination, 2km using that ticket.Now, you have a large group of friends and they want to reach to different distance. You think that you are smart enough that you can buy tickets that should manage all to reach their destination spending the minimum amount of coins. Then tell us how much we should at least pay to reach our destination.InputThere are multiple test cases. Each case start with a integer n, the total number of people in that group. 0=n=1000. Then comes n integers, each of them stands for a distance one of the men of the group wants to go to. You can assume that the distance a man wants to go is always less than 10000.OutputYour program should print a single integer for a single case, the minimum amount of coins the group should spend to reach to the destination of all the members of that group.Sample Input212223Sample Output24G：Max Sum IITime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2014Accepted Submission(s): 260Problem DescriptionGiven a sequence a1,a2,a3.an, you can cut the sequence into one or more consecutive sub-sequences as you want, for example, you can cut them into (a1.aj), (ak.al), (am.an),1jklmn. Your job is to make the maximum sum using the least number of consecutive sub-sequences. For example, given (6,-1，0, -2, 3), the max sum in this sequence is 9, the number of sub-sequences is 2 not 3, they are(6), (3).InputThe first line of the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1=N=1000000), then N integers followed(all the integers are between -1000 and 1000).OutputFor each test case, you should output two lines. The first line is Case #:, # means the number of the test case. The second line contains two integers, the number of consecutive sub-sequences and the max sum. Output a blank line between two cases.Sample Input22 6 -55 6 -1 0 -2 3Sample OutputCase 1:1 6Case 2:2 9H：TriangleTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 640Accepted Submission(s): 241Problem DescriptionK likes to play with the balls.That day he piled a triangle (n layers, layer 1 start,the first layer has 1 ball,the secode layer has 2 balls,the nth layer has n balls), but he felt uncomfortable after completion, and want to pile a right triangle, because he felt that the number 4 is a lucky one (because of “si ji fa cai”). So he decided to use 4 times of the balls he just used as a right-edge side of the right triangle(the three edges have no common factor).He only to pile the three edges,that is the middle is empty.But there will not have so many balls,so he wants to know the minimum of balls he must use.Now ,he turn to you for help.InputThe layer of the triangle as the promble describes n,1 = n 216OutputThe minimum of balls he must use and the length of the hypotenuse. One case one line Sample Input123Sample Output9 527 1353 25The second case:Let the right_edge promble describles is b ,The layer is 2,so b is 4 * (1 + 2) = 12.wo can know the edges of right triangle is 5 , 12 ,13.So the minimum of balls he must use is (5 + 12 + 13 3) = 27Subway upgradeTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 69Accepted Submission(s): 15Problem DescriptionAs we all know, one of the most important inventions for modern-day public transportation is the subway, which brings much convenience to our daily-life and saves us from the congested traffic.However, to hold the next ACM regional contest, you, as the mayor of city X, decided to upgrade the subway system of that city. There are some stations and roads in the city now, any road has a cost. To save money, you decided not to construct every road, but to make sure that there exist a path between every two stations.Sorry, the mission isnt completed. You know, there are n stations in the city,some contestants visit other stations regularly to admire some so-called big cows. Being naturally averse to spending hours each day on commuting, you should help them to find a place to live for which the total travel time is minimal.Every road has an ID, from 1 to m. If there are multiple approaches leading to the same minimal cost, the mayor prefers the o