[理学]杭电ACM题目

《[理学]杭电ACM题目》由会员分享，可在线阅读，更多相关《[理学]杭电ACM题目（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 isw

47、here 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 to that shown bel

48、ow. Sample Outputn e - - 0 1 1 2 2 2.5 3 2.666666667 4 2.708333333 SourceGreater New York 2000Digital RootsTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 20892 Accepted Submission(s): 6201Problem DescriptionThe digital root of a positive integer

49、is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.For ex

50、ample, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 ye

51、ilds 3, a single digit and also the digital root of 39. InputThe input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero. OutputFor each integer in the input, output its digital root on a separate line of the output. Sampl

52、e Input24 39 0 Sample Output6 3Uniform GeneratorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6236 Accepted Submission(s): 2485Problem DescriptionComputer simulations often require random numbers. One way to generate pseudo-random numbers is via

53、 a function of the formseed(x+1) = seed(x) + STEP % MODwhere % is the modulus operator.Such a function will generate pseudo-random numbers (seed) between 0 and MOD-1. One problem with functions of this form is that they will always generate the same pattern over and over. In order to minimize this e

54、ffect, selecting the STEP and MOD values carefully can result in a uniform distribution of all values between (and including) 0 and MOD-1.For example, if STEP = 3 and MOD = 5, the function will generate the series of pseudo-random numbers 0, 3, 1, 4, 2 in a repeating cycle. In this example, all of t

55、he numbers between and including 0 and MOD-1 will be generated every MOD iterations of the function. Note that by the nature of the function to generate the same seed(x+1) every time seed(x) occurs means that if a function will generate all the numbers between 0 and MOD-1, it will generate pseudo-ra

56、ndom numbers uniformly with every MOD iterations.If STEP = 15 and MOD = 20, the function generates the series 0, 15, 10, 5 (or any other repeating series if the initial seed is other than 0). This is a poor selection of STEP and MOD because no initial seed will generate all of the numbers from 0 and

57、 MOD-1.Your program will determine if choices of STEP and MOD will generate a uniform distribution of pseudo-random numbers.InputEach line of input will contain a pair of integers for STEP and MOD in that order (1 = STEP, MOD = 100000).OutputFor each line of input, your program should print the STEP

58、 value right- justified in columns 1 through 10, the MOD value right-justified in columns 11 through 20 and either Good Choice or Bad Choice left-justified starting in column 25. The Good Choice message should be printed when the selection of STEP and MOD will generate all the numbers between and in

59、cluding 0 and MOD-1 when MOD numbers are generated. Otherwise, your program should print the message Bad Choice. After each output test set, your program should print exactly one blank line.Sample Input3 5 15 20 63923 99999Sample Output3 5 Good Choice 15 20 Bad Choice 63923 99999 Good ChoiceSafecrac

60、kerTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2803 Accepted Submission(s): 1445Problem Description= Op tech briefing, 2002/11/02 06:42 CST =The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extr

61、emely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Kleins secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an en

62、graved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal posi