[工学]acm浙大简单题目.doc

1037 GridlandBackgroundFor 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.ProblemThe 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 NorthSouth or EastWest 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.InputThe 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.OutputThe 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 Input22 22 3Sample OutputScenario #1:4.00Scenario #2:6.00 1048 I Think I Need a HouseboatFred 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. 1051 A New Growth IndustryA 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 squares 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 squares density will change by DK (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 D0 to D15, separated from one another by one or more blanks. Each integer will be in the range -33, 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 03, 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: 12 0 1 1 1 2 1 0 -1 -1 -1 -2 -2 -3 -3 -3 -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 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 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 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 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 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 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 Sample Output: #!. #!. !. . . . . .!. .!#!. .!#X#!. .!#!. .!. . . . . . . . . 1067 Color Me LessProblemA color reduction is a mapping from a set of discrete colors to a smaller one. The solution to this problem requires that you perform just such a mapping in a standard twenty-four bit RGB color space. The input consists of a target set of sixteen RGB color values, and a collection of arbitrary RGB colors to be mapped to their closest color in the target set. For our purposes, an RGB color is defined as an ordered triple (R,G,B) where each value of the triple is an integer from 0 to 255. The distance between two colors is defined as the Euclidean distance between two three-dimensional points. That is, given two colors (R1,G1,B1) and (R2,G2,B2), their distance D is given by the equationThe input file is a list of RGB colors, one color per line, specified as three integers from 0 to 255 delimited by a single space. The first sixteen colors form the target set of colors to which the remaining colors will be mapped. The input is terminated by a line containing three -1 values.OutputFor each color to be mapped, output the color and its nearest color from the target set.Example Input0 0 0255 255 2550 0 11 1 1128 0 00 128 0128 128 00 0 128126 168 935 86 34133 41 193128 0 1280 128 128128 128 128255 0 00 1 00 0 0255 255 255253 254 25577 79 13481 218 0-1 -1 -1Output(0,0,0) maps to (0,0,0)(255,255,255) maps to (255,255,255)(253,254,255) maps to (255,255,255)(77,79,134) maps to (128,128,128)(81,218,0) maps to (126,168,9)1115 Digital RootsBackgroundThe 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.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.ExampleInput24390Output631151 Word ReversalFor each list of words, output a line with each word reversed without changing the order of the words.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.InputYou will be given a number of test cases. The first line contains a positive integer indicating the number of cases to follow. Each case is given on a line containing a list of words separated by one space, and each word contains only uppercase and lowercase letters.OutputFor each test case, print the output on one line.Sample Input13I am happy todayTo be or not to beI want to win the practice contestSample OutputI ma yppah yadotoT eb ro ton ot ebI tnaw ot niw eht ecitcarp tsetnoc1201 InversionLet A1,A2,.,An be a permutation of the set 1,2,., n. If i 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 table2 3 6 4 0 2 2 1 0since 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 Halls 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:9P 5 9 1 8 2 6 4 7 39I 2 3 6 4 0 2 2 1 00Sample Output:2 3 6 4 0 2 2 1 05 9 1 8 2 6 4 7 31205 Martian AdditionIn 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, youre 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:Youre 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:1234567890abcdefghij99999jjjjj9999900001Sample Output:bdfi02467jiiiij000001216 DeckScenarioA single playing card can be placed on a table, carefully, so that the short edges of the card are parallel to the tables edge, and half the length of the card hangs over the edge of the table. If the card hung any further out, with its center of gravity off the table, it would fall off the table and flutter to the floor. The same reasoning applies if the card were placed on another card, rather than on a table. Two playing cards can be arranged, carefully, with short edges parallel to table edges, to extend 3/4 of a card length beyond the edge of the table. The top card hangs half a card length past the edge of the bottom card. The bottom card hangs with only 1/4 of its length past the tables edge. The center of gravity of the two cards combined lies just over the edge of the table. Three playing cards can be arranged, with short edges parallel to table edges, and each card touching at most one other card, to extend 11/12 of a card length beyond the edge of the table. The top two cards extend 3/4 of a card length beyond the edge of the bottom card, and the bottom card extends only 1/6 over the tables edge; the center of gravity of the three cards lines over the edges of the table. If you keep stacking cards so that the edges are aligned and every card has at most one card above it and one below it, how far out can 4 cards extend over the tables edge? Or 52 cards? Or 1000 cards? Or 99999?InputInput contains several nonnegative integers, one to a line. No integer exceeds 99999.OutputThe standard output will contain, on successful completion of the program, a heading: # Cards Overhang (thats two spaces between the words) and, following, a line for each input integer giving the length of the longest overhang achievable with the given number of cards, measured in cardlengths, and rounded to the nearest thousandth. The length must be expressed with at least one digit before the decimal point and exactly three digits after it. The number of cards is right-justified in column 5, and the decimal points for the lengths lie in column 12.Sample Input1 2 3 4 30 Sample OutputThe line of digits is intended to guide you in proper output alignment, and is not part of the output that your solution should produce. 12345678901234567 # Cards Overhang 10.500 20.750 30.917 41.042 30 1.9971240 IBM Minus oneYou 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 du