# ACM C++简单题

Time Limit: 2 Seconds Memory Limit: 65536 KB

When chomping a tree the beaver cuts a very specific shape out of the tree trunk. What is left in the tree trunk looks like two frustums of a cone joined by a cylinder with the diameter the same as its height. A very curious beaver tries not to demolish a tree but rather sort out what should be the diameter of the cylinder joining the frustums such that he chomped out certain amount of wood. You are to help him to do the calculations.

We will consider an idealized beaver chomping an idealized tree. Let us assume that the tree trunk is a cylinder of diameter D and that the beaver chomps on a segment of the

trunk also of height D. What should be the diameter d of the inner cylinder such that the beaver chomped out V cubic units of wood?

Input Input contains multiple cases each presented on a separate line. Each line contains two integer numbers D and V separated by whitespace. D is the linear units and V is in cubic units. V will not exceed the maximum volume of wood that the beaver can chomp. A line with D=0 and V=0 follows the last case.

Output For each case, one line of output should be produced containing one number rounded to three fractional digits giving the value of d measured in linear units.

Sample Input 10 250 20 2500 25 7000 50 50000 00

Sample Output 8.054 14.775 13.115 30.901

Calculate a + b

Input
The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line.

Output
For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.

Sample Input
1 5

Sample Output
6

Hint
Use + operator： 题 3：

Gridland
Time Limit: 2 Seconds Memory Limit: 65536 KB

Background For years, computer scientists have been trying to find efficient solutions to different computing problems. For some of them efficient algorithms are already available, these are the "easy" problems like sorting, evaluating a polynomial or finding the shortest path in a graph. For the "hard" ones only exponential-time algorithms are known. The traveling-salesman problem belongs to this latter group. Given a set of N towns and roads between these towns, the problem is to compute the shortest path allowing a salesman to visit each of the towns once and only once and return to the starting point.

Problem The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast,

provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions North-South or East-West is 1 unit. The length of the roads is measured by the Euclidean distance. For example, Figure 7 shows 2 * 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 * 3-Gridland, the shortest tour has length 6.

Figure 7: A traveling-salesman tour in 2 * 3-Gridland. Input The first line contains the number of scenarios. For each scenario, the grid dimensions m and n will be given as two integer numbers in a single line, separated by a single blank, satisfying 1 < m < 50 and 1 < n < 50.

Output The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. In the next line, print the length of the shortest traveling-salesman tour rounded to two decimal digits. The output for every scenario ends with a blank line.

Sample Input 2 22 23

Sample Output Scenario #1: 4.00

Scenario #2: 6.00 题 4：

Financial Management
Time Limit: 2 Seconds Memory Limit: 65536 KB

Larry graduated this year and finally has a job. He's making a lot of money, but somehow never seems to have enough. Larry has decided that he needs to grab hold of his financial portfolio and solve his financing problems. The first step is to figure out what's been going on with his money. Larry has his bank account statements and wants to see how much money he has. Help Larry by writing a program to take his closing balance from each of the past twelve months and calculate his average account balance.

Input Format: The input will be twelve lines. Each line will contain the closing balance of his bank account for a particular month. Each number will be positive and displayed to the penny. No dollar sign will be included.

Output Format: The output will be a single number, the average (mean) of the closing balances for the twelve months. It will be rounded to the nearest penny, preceded immediately by a dollar sign, and followed by the end-of-line. There will be no other spaces or characters in the output.

Sample Input: 100.00 489.12 12454.12 1234.10 823.05 109.20 5.27 1542.25 839.18 83.99 1295.01 1.75

Sample Output: \$1581.42 题 5：

I Think I Need a Houseboat
Time Limit: 2 Seconds Memory Limit: 65536 KB

Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square miles each year, due to erosion caused by the Mississippi River. Since Fred is hoping to live in this house the rest of his life, he needs to know if his land is going to be lost to erosion.

After doing more research, Fred has learned that the land that is being lost forms a semicircle. This semicircle is part of a circle centered at (0,0), with the line that bisects the circle being the X axis. Locations below the X axis are in the water. The semicircle has an area of 0 at the beginning of year 1. (Semicircle illustrated in the Figure.)

Input Format: The first line of input will be a positive integer indicating how many data sets will be included (N). Each of the next N lines will contain the X and Y Cartesian coordinates of the land Fred is considering. These will be floating point numbers measured in miles. The Y coordinate will be non-negative. (0,0) will not be given.

Output Format: For each data set, a single line of output should appear. This line should take the form of: ? Property N: This property will begin eroding in year Z.? ? ? Where N is the data set (counting from 1), and Z is the first year (start from 1) this property will be within the semicircle AT THE END OF YEAR Z. Z must be an integer. After the last data set, this should print out ? END OF OUTPUT.? ? ? Notes: 1. No property will appear exactly on the semicircle boundary: it will either be inside or outside. 2. This problem will be judged automatically. Your answer must match exactly, including

the capitalization, punctuation, and white-space. This includes the periods at the ends of the lines. 3. All locations are given in miles.

Sample Input: 2 1.0 1.0 25.0 0.0

Sample Output: Property 1: This property will begin eroding in year 1. Property 2: This property will begin eroding in year 20. END OF OUTPUT. 题 6：

A New Growth Industry
Time Limit: 2 Seconds Memory Limit: 65536 KB

A biologist experimenting with DNA modification of bacteria has found a way to make bacterial colonies sensitive to the surrounding population density. By changing the DNA, he is able to "program" the bacteria to respond to the varying densities in their immediate neighborhood. The culture dish is a square, divided into 400 smaller squares (20x20). Population in each small square is measured on a four point scale (from 0 to 3). The DNA information is represented as an array D, indexed from 0 to 15, of integer values and is interpreted as follows:

In any given culture dish square, let K be the sum of that square's density and the densities of the four squares immediately to the left, right, above and below that square (squares outside the dish are considered to have density 0). Then, by the next day, that dish square's density will change by D[K] (which may be a positive, negative, or zero value). The total density cannot, however, exceed 3 nor drop below 0. Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [-3, -3, ..., -3]). Others result in immediate population explosions (e.g., [3,3,3, ..., 3]), and others are just plain boring (e.g., [0, 0, ... 0]). The biologist is interested in how some of the less obvious DNA programs might behave. Write a program to simulate the culture growth, reading in the number of days to be simulated, the DNA rules, and the initial population densities of the dish.

Input Format: Input to this program consists of three parts: 1. The first line will contain a single integer denoting the number of days to be simulated. 2. The second line will contain the DNA rule D as 16 integer values, ordered from D[0] to D[15], separated from one another by one or more blanks. Each integer will be in the range -3...3, inclusive. 3. The remaining twenty lines of input will describe the initial population density in the culture dish. Each line describes one row of squares in the culture dish, and will contain 20 integers in the range 0...3, separated from one another by 1 or more blanks.

Output Format: The program will produce exactly 20 lines of output, describing the population densities in the culture dish at the end of the simulation. Each line represents a row of squares in the culture dish, and will consist of 20 characters, plus the usual end-of-line terminator. Each character will represent the population density at a single dish square, as follows:

No other characters may appear in the output.

This problem contains multiple test cases! The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input:

1 2 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-1 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-2 -3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-3 -3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output:

##!................. #!.................. !................... .................... .................... .................... .................... .........!.......... ........!#!......... .......!#X#!........ ........!#!......... .........!.......... .................... .................... .................... .................... .................... .................... .................... ....................

Digital Roots
Time Limit: 2 Seconds Memory Limit: 65536 KB

Background The digital root of a positive integer 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 example, 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 yeilds 3, a single digit and also the digital root of 39.

Input The 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.

Output For each integer in the input, output its digital root on a separate line of the output.

Example Input

24 39 0
Output

6 3

Inversion
Time Limit: 2 Seconds Memory Limit: 65536 KB

Let { A1,A2,...,An } be a permutation of the set{ 1,2,..., n}. If i < j and Ai > Aj then the pair (Ai,Aj) is called an "inversion" of the permutation. For example, the permutation {3, 1, 4, 2} has three inversions: (3,1), (3,2) and (4,2). The inversion table B1,B2,...,Bn of the permutation { A1,A2,...,An } is obtained by letting Bj be the number of elements to the left of j that are greater than j. (In other words, Bj is the number of inversions whose second component is j.) For example, the permutation: { 5,9,1,8,2,6,4,7,3 } has the inversion table 236402210 since there are 2 numbers, 5 and 9, to the left of 1; 3 numbers, 5, 9 and 8, to the left of 2; etc. Perhaps the most important fact about inversions is Marshall Hall's observation that an inversion table uniquely determines the corresponding permutation. So your task is to convert a permutation to its inversion table, or vise versa, to convert from an inversion table to the corresponding permutation.

Input: The input consists of several test cases. Each test case contains two lines. The first line contains a single integer N ( 1 <= N <= 50) which indicates the number of elements in the permutation/invertion table. The second line begins with a single charactor either 'P', meaning that the next N integers form a permutation, or 'I', meaning that the next N integers form an inversion table. Following are N integers, separated by spaces. The input is terminated by a line contains N=0. Output: For each case of the input output a line of intergers, seperated by a single space (no space at the end of the line). If the input is a permutation, your output will be the corresponding inversion table; if the input is an inversion table, your output will be the corresponding permutation. Sample Input:

9 P 5 9 1 8 2 6 4 7 3 9 I 2 3 6 4 0 2 2 1 0 0
Sample Output:

2 3 6 4 0 2 2 1 0 5 9 1 8 2 6 4 7 3

Martian Addition
Time Limit: 2 Seconds Memory Limit: 65536 KB

In the 22nd Century, scientists have discovered intelligent residents live on the Mars. Martians are very fond of mathematics. Every year, they would hold an Arithmetic Contest on Mars (ACM). The task of the contest is to calculate the sum of two 100-digit numbers, and the winner is the one who uses least time. This year they also invite people on Earth to join the contest. As the only delegate of Earth, you're sent to Mars to demonstrate the power of mankind. Fortunately you have taken your laptop computer with you which can help you do the job quickly. Now the remaining problem is only to write a short program to calculate the sum of 2 given numbers. However, before you begin to program, you remember that the Martians use a 20-based number system as they usually have 20 fingers. Input:

You're given several pairs of Martian numbers, each number on a line. Martian number consists of digits from 0 to 9, and lower case letters from a to j (lower case letters starting from a to present 10, 11, ..., 19). The length of the given number is never greater than 100. Output: For each pair of numbers, write the sum of the 2 numbers in a single line. Sample Input:

1234567890 abcdefghij 99999jjjjj 9999900001
Sample Output:

bdfi02467j iiiij00000

IBM Minus One
Time Limit: 2 Seconds Memory Limit: 65536 KB

You may have heard of the book '2001 - A Space Odyssey' by Arthur C. Clarke, or the film of the same name by Stanley Kubrick. In it a spaceship is sent from Earth to Saturn. The crew is put into stasis for the long flight, only two men are awake, and the ship is controlled by the intelligent computer HAL. But during the flight HAL is acting more and more strangely, and even starts to kill the crew on board. We don't tell you how the story ends, in case you want to read the book for yourself :-) After the movie was released and became very popular, there was some discussion as to what the name 'HAL' actually meant. Some thought that it might be an abbreviation for 'Heuristic ALgorithm'. But the most popular explanation is the following: if you replace every letter in the word HAL by its successor in the alphabet, you get ... IBM. Perhaps there are even more acronyms related in this strange way! You are to write a program that may help to find this out.

Input The input starts with the integer n on a line by itself - this is the number of strings to follow. The following n lines each contain one string of at most 50 upper-case letters.

Output For each string in the input, first output the number of the string, as shown in the sample output. The print the string start is derived from the input string by replacing every time by the following letter in the alphabet, and replacing 'Z' by 'A'. Print a blank line after each test case.

Sample Input 2 HAL SWERC

Sample Output String #1 IBM String #2 TXFSD 题 11：

Carbon Dating
Time Limit: 2 Seconds Memory Limit: 65536 KB

Until the second half of the 20th century, determining the actual age of an archaeological find had been more or less a matter of educated guessing. Comparing finds to previous, already dated, ones and evaluation of the surroundings of a find were the best available techniques. But nowadays, there is a much more reliable method: carbon dating. Carbon dating works as follows: Naturally occurring carbon is a mixture of stable isotope (mostly 12C) and the unstable, radioactive, isotope 14C. The ratio between the two is almost constant in living organisms: 14C slowly decays, but at the same time, the radiation of the sum produces the same amount in the upper atmosphere, which is taken in by the organisms. But when, for example, a tree is felled and made to wood, it does not receive any new 14C, and the amount present in the wood becomes less and less due to radioactive decay. In

this problem, you are to write a program that uses information about the amount of remaining 14C to determine the approximate age of sample. The following facts must be used: The amount of 14C present in a sample halves every 5730 years (this is called the half-life of 14C). The rate of decay (measured in decays per hour per gram of carbon) is proportional to the amount of 14C left in the sample. In living organisms (age zero), there are 810 decays per hour per gram of carbon. So, for example, if we measure in a sample of one gram of carbon 405 decays per hour, we know that it is approximately 5730 years old.

Input The input contains the measurements taken of several samples we want to date. Every line contains two positive integers, w and d. w is the amount of carbon in the sample, measured in grams, and d is the number of decays measured over one hour. The input is terminated by a test case starting with w = d = 0.

Output For each sample description in the input, first output the numnber of the sample, as shown in the sample output.Then print the approximate age in the format The approximate age is x years.

If the age is less than 10,000 years, x should be rounded to the colsest multiple of 100 years (rounding up in case of a tie). If the age is more than 10,000 years, round it to the closest multiple of 1000 years (again rounding up in case of a tie). Print a blank line after each sample.

Sample Input 1 405 5 175 00

Sample Output Sample #1 The approximate age is 5700 years. Sample #2 The approximate age is 26000 years. 题 12：

A Simple Task
Time Limit: 2 Seconds Memory Limit: 65536 KB

Given a positive integer n and the odd integer o and the nonnegative integer p such that n = o2^p.

Example For n = 24, o = 3 and p = 3.

Task Write a program which for each data set: reads a positive integer n, computes the odd integer o and the nonnegative integer p such that n = o2^p,

writes the result.

Input The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 10. The data sets follow. Each data set consists of exactly one line containing exactly one integer n, 1 <= n <= 10^6.

Output The output should consists of exactly d lines, one line for each data set. Line i, 1 <= i <= d, corresponds to the i-th input and should contain two integers o and p separated by a single space such that n = o2^p.

Sample Input 1 24

Sample Output 33 题 13：

When Can We Meet?
Time Limit: 2 Seconds Memory Limit: 65536 KB

The ICPC committee would like to have its meeting as soon as possible to address every little issue of the next contest. However, members of the committee are so busy maniacally developing (possibly useless) programs that it is very difficult to arrange their schedules for the meeting. So, in order to settle the meeting date, the chairperson requested every member to send back a list of convenient dates by E-mail. Your mission is to help the chairperson, who is now dedicated to other issues of the contest, by writing a program that chooses the best date from the submitted lists. Your program should find the

date convenient for the most members. If there is more than one such day, the earliest is the best.

Input The input has multiple data sets, each starting with a line containing the number of committee members and the quorum of the meeting. NQ Here, N, meaning the size of the committee, and Q meaning the quorum, are positive integers. N is less than 50, and, of course, Q is less than or equal to N. N lines follow, each describing convenient dates for a committee member in the following format. M Date1 Date2 ... DateM Here, M means the number of convenient dates for the member, which is an integer greater than or equal to zero. The remaining items in the line are his/her dates of convenience, which are positive integers less than 100, that is, 1 means tomorrow, 2 means the day after tomorrow, and so on. They are in ascending order without any repetition and separated by a space character. Lines have neither leading nor trailing spaces. A line containing two zeros indicates the end of the input.

Output For each data set, print a single line containing the date number convenient for the largest number of committee members. If there is more than one such date, print the earliest. However, if no dates are convenient for more than or equal to the quorum number of members, print 0 instead.

Sample Input 32 214 0 3348 32 41589

3259 524579 33 214 3259 224 33 212 3129 224 00

Sample Output 4 5 0 2 题 14：

Biker's Trip Odometer
Time Limit: 2 Seconds Memory Limit: 65536 KB

Most bicycle speedometers work by using a Hall Effect sensor fastened to the front fork of the bicycle. A magnet is attached to one of the spokes on the front wheel so that it will line up with the Hall Effect switch once per revolution of the wheel. The speedometer monitors the sensor to count wheel revolutions. If the diameter of the wheel is known, the distance traveled can be easily be calculated if you know how many revolutions the wheel has made. In addition, if the time it takes to complete the revolutions is known, the average speed can also be calculated. For this problem, you will write a program to determine the total distance traveled (in miles) and the average speed (in Miles Per Hour) given the wheel diameter, the number of revolutions and the total time of the trip. You can assume that the front wheel never leaves the ground, and there is no slipping or skidding.

Input Input consists of multiple datasets, one per line, of the form: diameter revolutions time

The diameter is expressed in inches as a floating point value. The revolutions is an integer value. The time is expressed in seconds as a floating point value. Input ends when the value of revolutions is 0 (zero).

Output For each data set, print: Trip #N: distance MPH Of course N should be replaced by the data set number, distance by the total distance in miles (accurate to 2 decimal places) and MPH by the speed in miles per hour (accurate to 2 decimal places). Your program should not generate any output for the ending case when revolutions is 0. Constants For p use the value: 3.1415927. There are 5280 feet in a mile. There are 12 inches in a foot. There are 60 minutes in an hour. There are 60 seconds in a minute. There are 201.168 meters in a furlong.

Sample Input 26 1000 5 27.25 873234 3000 26 0 1000

Sample Output Trip #1: 1.29 928.20 Trip #2: 1179.86 1415.84

Adding Reversed Numbers
Memory Limit: 65536 KB

Time Limit: 2 Seconds

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to

transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play. Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros. ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

Input The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

Sample Input 3 24 1 4358 754 305 794

Sample Output 34 1998 1

Filling Out the Team
Time Limit: 2 Seconds Memory Limit: 65536 KB

Over the years, the people of the great city of Pittsburgh have repeatedly demonstrated a collective expertise at football second to none. Recently a spy has discovered the true source of the city's football power-a wizard known only as "Myron," who is infallible at selecting the proper position at which each player will excel. Now that you know the source of Pittsburgh's wisdom, you are determined to provide your school's football team with a computer program that matches the wisdom of "Myron." You have consulted with the best football minds you can find, and they have dispensed their wisdom on the slowest speed, minimum weight, and minimum strength required to play each position.
Position Slow.Speed Min.Weight Min.Strength 150 300 200 200 500 300

Wide Receiver 4.5 Lineman Quarterback 6.0 5.0

Using this knowledge, you will develop a program that reads in several players physical attributes and outputs what position(s) they are able to play.

Input Each line of the input file will list the attributes for one player: <speed> <weight> <strength> Each number will be a real-valued number. The file will end with a line reading "0 0 0".

Output For each player, you will output one line listing the positions that player can play. A player can play a position if each of their attributes is greater or equal to the minimum for weight and strength, and less than or equal to the slowest speed. If a player can play multiple positions, output them in the order listed above, separated by whitespace. You can not

leave an extra space at the end of the line. If a player can play no positions, write "No positions" on the line.

Sample Input 4.4 180 200 5.5 350 700 4.4 205 350 5.2 210 500 000

Sample Output Wide Receiver Lineman Wide Receiver Quarterback No positions 题 17：

Electrical Outlets
Time Limit: 2 Seconds Memory Limit: 65536 KB

Roy has just moved into a new apartment.Well, actually the apartment itself is not very new, even dating back to the days before people had electricity in their houses. Because of this, Roy? s apartment has only one single wall outlet, so Roy can only power one of ? his electrical appliances at a time. Roy likes to watch TV as he works on his computer, and to listen to his HiFi system (on high volume) while he vacuums, so using just the single outlet is not an option. Actually, he wants to have all his appliances connected to a powered outlet, all the time. The answer, of course, is power strips, and Roy has some old ones that he used in his old apartment. However, that apartment had many more wall outlets, so he is not sure whether his power strips will provide him with enough outlets now. Your task is to help Roy compute how many appliances he can provide with electricity, given a set of power strips. Note that without any power strips, Roy can power one single appliance through the wall outlet. Also, remember that a power strip has to be powered itself to be of any use.

Input Input vill start with a single integer 1 ≤ N ≤ 20, indicating the number of test cases to follow. Then follow N lines, each describing a test case. Each test case starts with an integer 1 ≤ K ≤ 10, indicating the number of power strips in the test case. Then follow, on the same line, K integers separated by single spaces, O1O2...OK , where 2 ≤ Oi ≤ 10, indicating the number of outlets in each power strip. Output Output one line per test case, with the maximum number of appliances that can be powered. Sample Input 3 3234 10 4 4 4 4 4 4 4 4 4 4 4 10 10 10 10 Sample Output 7 31 37 题 18：

Hanoi Tower
Time Limit: 2 Seconds Memory Limit: 65536 KB

You all must know the puzzle named "The Towers of Hanoi". The puzzle has three pegs (peg 1, peg 2 and peg 3) and N disks of different radii. Initially all disks are located on the first peg, ordered by their radii - the largest at the bottom, the smallest at the top. In each turn you may take the topmost disc from any peg and move it to another peg, the only rule says that you may not place the disc atop any smaller disk. The problem is to move all disks to the last peg (peg 3). I use two different integers a (1 <= a <= 3) and b (1 <= b <= 3) to indicate a move. It means to move the topmost disk of peg a to the top of peg b. A move is valid if and only if there is at least one disk on peg a and the topmost disk of peg a can be moved on the peg b without breaking the former rule. Give you some moves of a game, can you give out the result of the game?

Input Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 55) which is the number of test cases. And it will be followed by T consecutive test cases. The first line of each test case is a single line containing 2 integers n (1 <= n <= 10) and m (1 <= m <= 12000) which is the number of disks and the number of the moves. Then m lines of moves follow. Output For each test case, output an integer in a single line according to the result of the moves. Note: (1) If there is an invalid move before all disks being on peg 3 and the invalid move is the p-th move of this case (start from 1) , output the integer -p please and the moves after this move(if any) are ignored. (2) If after the p-th move all disks are on peg 3 without any invalid move, output the integer p please and the moves after this move (if any) are ignored. (3) Otherwise output the integer 0 please. Sample Input

3 2 1 1 2 2 1 1 3 2 1 1 3

3 2 3 3 3 2 3 2 3 3 2 2

Sample Output

3 -3 0

Easy Task
Time Limit: 2 Seconds Memory Limit: 65536 KB

Calculating the derivation of a polynomial is an easy task. Given a function f(x) , we use (f(x))' to denote its derivation. We use x^n to denote xn. To calculate the derivation of a polynomial, you should know 3 rules: (1) (C)'=0 where C is a constant. (2) (Cx^n)'=C*n*x^(n-1) where n>=1 and C is a constant. (3) (f1(x)+f2(x))'=(f1(x))'+(f2(x))'. It is easy to prove that the derivation a polynomial is also a polynomial. Here comes the problem, given a polynomial f(x) with non-negative coefficients, can you write a program to calculate the derivation of it? Input Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 1000) which is the number of test cases. And it will be followed by T consecutive test cases. There are exactly 2 lines in each test case. The first line of each test case is a single line containing an integer N (0 <= N <= 100). The second line contains N + 1 non-negative integers, CN, CN-1, ..., C1, C0, ( 0 <= Ci <= 1000), which are the coefficients of f(x). Ci is the coefficient of the term with degree i in f(x). (CN!=0) Output For each test case calculate the result polynomial g(x) also in a single line. (1) If g(x) = 0 just output integer 0.otherwise (2) suppose g(x)= Cmx^m+Cm-1x^(m-1)+...+C0 (Cm!=0),then output the integers Cm,Cm-1,...C0. (3) There is a single space between two integers but no spaces after the last integer. Sample Input

3 0 10 2 3 2 1 3 10 0 1 2

Sample Output

0 6 2 30 0 1

Faster, Higher, Stronger
Time Limit: 2 Seconds Memory Limit: 65536 KB

In the year 2008, the 29th Olympic Games will be held in Beijing. This will signify the prosperity of China and Beijing Olympics is to be a festival for people all over the world as well. The motto of Olympic Games is "Citius, Altius, Fortius", which means "Faster, Higher, Stronger".

In this problem, there are some records in the Olympic Games. Your task is to find out which one is faster, which one is higher and which one is stronger. Input Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 50) which is the number of test cases. And it will be followed by T consecutive test cases. Each test case has 3 lines. The first line is the type of the records, which can only be "Faster" "Higher" or "Stronger". The second line is a positive integer N meaning the number of the records in this test case. The third line has N positive integers, i.e. the records data. All the integers in this problem are smaller than 2008. Output

Results should be directed to standard output. The output of each test case should be a single integer in one line. If the type is "Faster", the records are time records and you should output the fastest one. If the type is "Higher", the records are length records. You should output the highest one. And if the type is "Stronger", the records are weight records. You should output the strongest one. Sample Input

3 Faster 3 10 11 12 Higher 4 3 5 4 2 Stronger 2 200 200
Sample Output

10 5 200

### ACM动态规划问题简易模板(C++可编译)

ACM动态规划问题简易模板(C++可编译)_计算机软件及应用_IT/计算机_专业资料。ACM竞赛是非常有趣的竞赛,动态规划是非常有意思的算法1...

### ACM练习加答案(值得一看)

Sample Input sin(1) cos(1) Sample Output 0.841471 0.540302 Hint C++...ACM大量习题题库及建议培... 42页 1下载券 ACM练习 10页 1下载券 ...

### ACM常用输入输出格式C++版

ACM常用输入输出格式C++版 - ACM 常用输入输出格式(C++) GuYue.Wang ①有多组数据输入,对应每组输入,每组输出占一行。 ②先输入一个整数表示有多少组数据,接着...

### ACM第三次培训题目及答案

ACM第三次培训题目及答案_IT/计算机_专业资料。ACM第三次培训题目及答案 ACM第...(c++ ? " %d" : "%d", b + m - 1); b += m * 2; } printf(...