《[理学]杭电ACM题目.doc》由会员分享，可在线阅读，更多相关《[理学]杭电ACM题目.doc（55页珍藏版）》请在三一办公上搜索。
1、A + B ProblemTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 151346 Accepted Submission(s): 47937Problem DescriptionCalculate A + B. InputEach line will contain two integers A and B. Process to end of file. OutputFor each case, output A + B in one
2、 line. Sample Input1 1 Sample Output2Sum ProblemTime Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 114332 Accepted Submission(s): 26200Problem DescriptionHey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).In this problem, your task is to ca
3、lculate SUM(n) = 1 + 2 + 3 + . + n. InputThe input will consist of a series of integers n, one integer per line. OutputFor each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input1 100 Sample Output1 5050A +
4、 B Problem IITime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 79807 Accepted Submission(s): 14884Problem DescriptionI have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. InputThe first line of
5、the input contains an integer T(1=T=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer
6、will not exceed 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 is the an equation A + B = Sum, Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two tes
7、t cases. Sample Input2 1 2 112233445566778899 998877665544332211 Sample OutputCase 1: 1 + 2 = 3 Case 2: 112233445566778899 + 998877665544332211 = 1111111111111111110Max SumTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 55141 Accepted Submission(s
8、): 12401Problem DescriptionGiven a sequence a1,a2,a3.an, your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. InputThe first line of the input contains an integer T(1=T=20) which means the number of test case
9、s. Then T lines follow, each line starts with a number N(1=N=100000), 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 three integers,
10、 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 first one. Output a blank line between two cases. Sample Input2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5 Sample OutputCase 1: 14 1 4 Case 2: 7 1 6Let the
11、Balloon RiseTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 30799 Accepted Submission(s): 10110Problem DescriptionContest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges favorite time is guessing
12、 the most popular problem. When the contest is over, they will count the balloons of each color and find the result.This year, they decide to leave this lovely job to you. InputInput contains multiple test cases. Each test case starts with a number N (0 N = 1000) - the total number of balloons distr
13、ibuted. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.A test case with N = 0 terminates the input and this test case is not to be processed.OutputFor each case, print the color of balloon for the most popular problem on a single line. It i
14、s guaranteed that there is a unique solution for each test case. Sample Input5 green red blue red red 3 pink orange pink 0 Sample Outputred pinkNumber SequenceTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 41359 Accepted Submission(s): 8887Proble
15、m DescriptionA number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2) mod 7.Given A, B, and n, you are to calculate the value of f(n). InputThe input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 = A, B = 100
16、0, 1 = n = 100,000,000). Three zeros signal the end of input and this test case is not to be processed. OutputFor each test case, print the value of f(n) on a single line. Sample Input1 1 3 1 2 10 0 0 0 Sample Output2 5Tick and TickTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (
17、Java/Others)Total Submission(s): 3278 Accepted Submission(s): 847Problem DescriptionThe three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is
18、 at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy. InputThe input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1. OutputFor each D, p
19、rint in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places. Sample Input0 120 90 -1 Sample Output100.000 0.000 6.251 Quoit DesignTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9148 Acce
20、pted Submission(s): 2204Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only e
21、ncircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.Assume that all the toys are points on a plane. A point is encircled by the rin
22、g if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.InputThe input consists of several test cases. For each case, the first line contains an integer N (2 =
23、N = 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0. OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 deci
24、mal places.Sample Input2 0 0 1 1 2 1 1 1 1 3 -1.5 0 0 0 0 1.5 0 Sample Output0.71 0.00 0.75ElevatorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 16637 Accepted Submission(s): 8841Problem DescriptionThe highest building in our city has only one e
25、levator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.For a given request
26、 list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.InputThere are multiple test cases. Each case contains a positive integer N, followed
27、by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed. OutputPrint the total time on a single line for each test case. Sample Input1 2 3 2 3 1 0 Sample Output17 41FatMouse TradeTime Limit: 2000/10
28、00 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 16853 Accepted Submission(s): 5150Problem DescriptionFatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-t
29、h room contains Ji pounds of JavaBeans and requires Fi pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Ji* a% pounds of JavaBeans if he pays Fi* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell h
30、im the maximum amount of JavaBeans he can obtain.InputThe input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers Ji and Fi respectively. The last test case is followed by two
31、-1s. All integers are not greater than 1000. OutputFor each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain. Sample Input5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 Sample Output13.333 31.500Tempter o
32、f the BoneTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 24095 Accepted Submission(s): 6634Problem DescriptionThe doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the
33、doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time
34、 (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next se
35、cond. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.InputThe input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 N, M 7; 0 T 50), which denote th
36、e sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:X: a block of wall, which the doggie cannot enter;S: the start point of the doggie;D: the Door; or.: an empty
37、 block.The input is terminated with three 0s. This test case is not to be processed.OutputFor each test case, print in one line YES if the doggie can survive, or NO otherwise.Sample Input4 4 5 S.X. .X. .XD . 3 4 5 S.X. .X. .D 0 0 0 Sample OutputNO YESStarship TroopersTime Limit: 10000/5000 MS (Java/
38、Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2842 Accepted Submission(s): 704Problem DescriptionYou, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is actually a huge cavern, which consists of many rooms connected w
39、ith tunnels. Each room is occupied by some bugs, and their brains hide in some of the rooms. Scientists have just developed a new weapon and want to experiment it on some brains. Your task is to destroy the whole base, and capture as many brains as possible.To kill all the bugs is always easier than
40、 to capture their brains. A map is drawn for you, with all the rooms marked by the amount of bugs inside, and the possibility of containing a brain. The caverns structure is like a tree in such a way that there is one unique path leading to each room from the entrance. To finish the battle as soon a
41、s possible, you do not want to wait for the troopers to clear a room before advancing to the next one, instead you have to leave some troopers at each room passed to fight all the bugs inside. The troopers never re-enter a room where they have visited before.A starship trooper can fight against 20 b
42、ugs. Since you do not have enough troopers, you can only take some of the rooms and let the nerve gas do the rest of the job. At the mean time, you should maximize the possibility of capturing a brain. To simplify the problem, just maximize the sum of all the possibilities of containing brains for t
43、he taken rooms. Making such a plan is a difficult job. You need the help of a computer.InputThe input contains several test cases. The first line of each test case contains two integers N (0 N = 100) and M (0 = M = 100), which are the number of rooms in the cavern and the number of starship troopers
44、 you have, respectively. The following N lines give the description of the rooms. Each line contains two non-negative integers - the amount of bugs inside and the possibility of containing a brain, respectively. The next N - 1 lines give the description of tunnels. Each tunnel is described by two in
45、tegers, which are the indices of the two rooms it connects. Rooms are numbered from 1 and room 1 is the entrance to the cavern.The last test case is followed by two -1s.OutputFor each test case, print on a single line the maximum sum of all the possibilities of containing brains for the taken rooms.
46、Sample Input5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 1 1 20 7 -1 -1Sample Output50 7u Calculate eTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 12815 Accepted Submission(s): 5510Problem DescriptionA simple mathematical formula for e iswhere n is allowed to go to infinity. This can actually yield very accurate approximations of e using relatively small values of n. OutputOutput the approximations of e generated by the above formula for the values of n from 0 to 9. The beginning of your output should appear similar t
