IEE极限编程预赛题目.doc

Language:1246Hilbert Curve IntersectionsTime Limit:1000MSMemory Limit:10000KTotal Submissions:171Accepted:58DescriptionDavid Hilbert proved the existence of a very counter-intuitive curve that fills space. The construction of the Hilbert curve is based on a sequence of curves, H1, H2, H3, H4, . composed of horizontal and vertical segments. Each curve lies in the unit square 0, 1 * 0, 1. H1 contains just three segments, connecting the points (1/4, 3/4) to (1/4, 1/4) to (3/4, 1/4) to (3/4, 3/4). Hnis defined recursively in terms of Hn-1, for n = 2, 3, . by four transformations:1.Halve all coordinates in Hn-1.2.Add a copy rotated 90 degrees counterclockwise about the point (0, 1/2).3.Add the reflection across the line x = 1/2.4.Let m = 1/2n+1. Add segments connecting endpoints (1/2 - m, 1/2 - m) to (1/2 + m, 1/2 - m), (m, 1/2 - m) to (m, 1/2 + m), and (1 - m, 1/2 - m) to (1 - m, 1/2 + m).Your job is to count the number of intersections of horizontal line segments with these curves. For example, consider Figures 1 and 2, which illustrate the first two example input data sets below.The coordinates of vertices of Hn are odd multiples of 1/2n+1. The coordinates of horizontal segment endpoints will always be multiples of 1/2n. Hence the specified horizontal segment can only cross vertical segments in Hn.InputInput consists of one to 100 data sets, one per line, followed by a final line containing only 0. Each data set consists of four integers separated by blanks in the formn x1 x2 ywhich represents Hnand the segment from (x1/2n, y/2n) to (x2/2n, y/2n), where 0 n 31, x1 x2, and each of x1, x2, and y lie in the range 0 to 2n, inclusive.OutputThe output is one integer per line for each data set: the number of intersections of Hnwith the segment. Caution: A brute force solution that computes each intersection individually will not finish within the one minute time limit. As you can see below, there may be more than one billion intersections for any data set.Sample Input3 2 7 74 0 16 130 1 1073741823 10Sample Output3161073741822SourceMid-Central USA 20023766Hexagon Coin TossTime Limit:1000MSMemory Limit:65536KTotal Submissions:378Accepted:113DescriptionHexagon Coin Toss is a simple game played on a Hexagon chessboard. Players toss a coin on the chessboard and see how many hexagons intersect with the coin. Now you are given a task to calculate the result of the coin toss-for each different number of intersecting hexagons, just output the probability.To simplify the problem, we assume that the side length of each hexagon is 1 and the radius of the coin will not exceed 0.5 (so that the coin can cover at most 3 hexagons).The chessboard contains several rows of hexagons and numbers of hexagons in all odd-number-row are the same (That is true for all even-number-rows). The chessboard is described as (N,M,K). HereNrepresenting the number of hexagons in the longest row. M representing the number of rows andKshows the number of hexagons in the first row. So the chessboard above can be represented as (4, 3, 3).The center of the coin will be in the chessboard and we do not take anything outside the chessboard into consideration. In the situation below, the coin covers 2 hexagons.InputThe input contains multiple test cases.The first line of each case contains three integersN,M,K, representing the size of the chessboard.NandMwill be in the range of 1，1000 andKequals eitherNorN-1. It is guaranteed that all input information is valid (So that (2, 1, 1) will not appear).The following line is a real numberR, the radius of the coin.Input is ended with a case ofN=M=K=0.OutputFor each test case, output the case number first.The following 3 lines are the result information, as shown in the sample output. The result should be rounded to 0.001.Print an empty line after each test case.Sample Input4 5 40.384 5 30.264 2 30.240 0 0Sample OutputCase 1:Probability of covering 1 hexagon = 48.303 percent.Probability of covering 2 hexagons = 31.300 percent.Probability of covering 3 hexagons = 20.397 percent.Case 2:Probability of covering 1 hexagon = 61.956 percent.Probability of covering 2 hexagons = 27.934 percent.Probability of covering 3 hexagons = 10.110 percent.Case 3:Probability of covering 1 hexagon = 72.550 percent.Probability of covering 2 hexagons = 22.220 percent.Probability of covering 3 hexagons = 5.230 percent.Source1070Language:Deformed WheelTime Limit:1000MSMemory Limit:10000KTotal Submissions:632Accepted:140DescriptionThe villages carpentry is located by a hill side. The carpenters two little boys play with a piece of wood which looks like a deformed wheel with two identical convex polygon-shaped faces. One boy sets the wooden wheel on a slope at the hill top and let it roll down. The other boy is to quickly place himself at where he guesses the rolling wood would stop. Your program is to help him make the right guess.More formally, we consider the wooden wheel as a simple convex polygon and we approximate the hill by a sequence of connected line segments with decreasing slopes. The slope of the last segment in the sequence is assumed to be zero, and the slope of the first segment is assumed to be a positive number. Initially, the wheel is placed on the hill such that there is at least one point of contact between the wheel and segments. For example in the following figure, the wheel in its initial position is drawn in solid lines, while the final position is drawn in dashed lines.At any instant, the wheel rotates around one of its vertices, say P, if the y-coordinate of its center of gravity is decreased (note that this condition is necessary at any instant during the motion). It can be easily shown that at any instant, there is at most one such vertex. Rotation around P is stopped when the wheel touches a segment. The motion continues until no vertex can be found such that the wheel can rotate around it. At any instant, assume that changing the position of the center of gravity in any direction for at most 10-5 units, does not affect the stability of the wheel. Also assume that the friction between the wheel and the surface of the hill is so high that the wheel never slides on the surface.InputThe first line of the input contains a single integer t (1 = t = 10), the number of test cases, followed by the input data for each test case. In the first line of each test case there is an integer n (1 = n = 10), that indicates the number of the wheel vertices. In each of the next n lines, there is a pair of numbers which are x and y coordinates of the initial position of a vertex. After this, there is a single line containing the initial x and y coordinates of the center of gravity of the wheel. You can assume that the center of gravity is inside or on the boundary of the polygon (note that the given center of gravity is not necessarily computable from wheels geometric shape). Next lines of the test data will describe the shape of the hill. The surface of the hill is approximated with a series of line segments with decreasing slopes ending with a horizontal line segment. For each segment, there is a line containing length and slope of a segment (both of them are real numbers). The lines are ordered in decreasing slope (The last line of this part of the input has slope zero). You can assume that the last (horizontal) line is long enough that the wheel would not pass its end. In the last line of the test case, there is a line containing the x and y coordinates of the right end-point of the first segment. All coordinates and slopes are real numbers.OutputFor each test case, there should be a single line in the output , containing two numbers which are x and y coordinates of the wheels center of gravity. Round the numbers in the output to 3 digits after decimal point.Sample Input1440 3030 3724 3030 2627 2930 1100 040 30Sample Output28.854 20.031Source2848Kindergarten GraduationTime Limit:1000MSMemory Limit:65536KTotal Submissions:678Accepted:271Special JudgeDescriptionThe WeeOnes Kindergarten has a strange ceremony as part of its graduation: The children line up with the girls on the left and the boys on the right with a single space between the boys and the girls. By making a sequence of the following four moves, the children are to end up with all the boys on the left and all the girls on the right with a single space between the boys and the girls.MoveOperationSlide left (s)The child to the right of the empty space moves into the emptyspace.Slide right (S)The child to the left of the empty space moves into the empty space.Hop left (h)The child two spaces to the right of the open space leapfrogs overthe intervening child to the open space.Hop right (H)The child two spaces to the left of the open space leapfrogs overthe intervening child to the open space.In each case, the previous position of the child who moved becomes the new open space.For example, with two girls and two boys we begin with:GG_BBthe following moves give the desired result:s: GGB_BH: G_BGBS: _GBGBh: BG_GBh: BGBG_S: BGB_GH: B_BGGs: BB_GGThe teacher would like this process to end in a reasonable amount of time so the parents can go home (the children are probably willing to do this all day). Write a program which takes as input the numbers of girls and boys (nGirlsandnBoysrespectively) and finds a sequence of at most (nGirls*nBoys+nGirls+nBoys) moves which takes you from the starting position to the ending position. Each girl must leapfrog over (or be leapfrogged over by) each boy and, on average, each child must move past the empty space.InputThe input begins with the number of problemsN, (1 N 1000), on a line by itself followed byNproblem instances each on its own line. A problem instance has the form:probNumbernGirlsnBoyswhereprobNumberincreases sequentially from 1 toN.nGirlsis the number of girls.nBoysis the number of boys.There is at least 1 child and at most 24 children in a class.OutputFor each problem instance, output the problem number at the beginning of the line then a single space, then the number of moves on a line. On each following line, output the codes for the required moves in order. Each line except the last should have 50 move characters with the remainder, if any, on the final line. The last line of a problem instance result should be a single blank line.Sample Input3 1 2 22 4 03 5 10Sample Output1 8sHShhSHs2 2HH3 65sHShhsHHHShhhhsHHHHHshhhhhsHHHHHshhhhhsHHHHHshhhhhSHHHHshhhSHHshSHintNote:Other solutions are possible; for instance:1. ShsHHshSis also a solution to problem 12. SSSS, HSS,etc. are also acceptable answers to problem 2.Source3289MoonshineTime Limit:1000MSMemory Limit:65536KTotal Submissions:599Accepted:116DescriptionGranny is preparing moonshine whiskey for an upcoming family reunion. Because her family is large, she needs to make several batches of whiskey, which she collects in a large metal cream can. After making, and sampling, several batches Granny stumbles and knocks the can on its side. Fortunately, the lid is tightly fixed so no whiskey is lost.Our question to you is this: assuming that the depth of whiskey in the can waskcm with the can sitting upright, what is its depth with the can lying horizontal? The can itself is made of two cylinders: the body with heighthband diameterdb, and the neck with heighthnand diameterdn. The neck and body are joined by a tapered conic shoulder such that the overall height of the can ish. The bottom and lid of the can are disks of diameterdbanddnrespectively.InputInput consists of several test cases. Each test case consists of a line containing real numbersk hbdbhndnandh.You may assume that100hhb+hnand that100dbdn. A line containing 0 0 0 0 0 0 follows the last test case.OutputFor each test case, output a line containingsthe depth with the can lying horizontally, rounded to two decimal places.Sample Input5.625 10.0 10.0 5.0 5.0 15.00 0 0 0 0 0Sample Output5.00Source3452Railway TransportationTime Limit:5000MSMemory Limit:65536KTotal Submissions:860Accepted:388Special JudgeDescriptionACM has created a new series of huge billboards. Now, they have to be transported using a train. Unfortunately, the carriages of the train get somehow mixed, but ACM wants the billboards to be delivered in an appropriate order.In a small example, we have 5 carriages approaching a railroad station with 3 parallel tracks. Each carriage may enter any track, but once it is there, it cannot go back anymore. At the other end, the tracks are merged back to a single railroad and cannot go back, again. We want the carriages to leave their tracks in the correct order.Possible solution is illustrated in the second figure. We may send carriage 4 to the first track, then the carriage number 2 to the second one, number 5 to the first, number 3 to the second, and finally, number 1 to the third track, which may immediately leave it to its correct position. The other carriages will follow as needed.Your task is to write a program that sends carriages to correct tracks and merges them at the other end. You may assume that the tracks are long enough to hold any number of carriages.InputThe input consists of several scenarios, each of them described on two lines. End of the input is signalized by two zeros.The first line of each scenario contains two positive integers N and M, separated with a space, N 200000, M 200000. N is the number of carriages, M is the number of tracks.The second line will contain N non-negative integers representing carriages and their intended order on the other end of the station. Some carriages may have identical numbers, in such a case, their mutual order is not significant.OutputFor each scenario, output two lines. The first line will contain N numbers, each of them between 1 and M inclusive. Each number corresponds to one carriage (in the order they were given in the input) and determines a track the carriage is to be moved to. The second line also contains N numbers, they specify from what tracks and in which order are the carriages sent to the other end of the station.If carriages are manipulated according to your answer, they must leave the station in a nondescending order. When there are more solutions, you may print any of them. If there is no solution, print only one line containing the words Transportation failed”.Sample Input5 34 2 5 3 15 35 4 3 2 10 0Sample Output1 2 1 2 33 2 2 1 1Transportation failedSource.3571GameTime Limit:5000MSMemory Limit:65536KTotal Submissions:312Accepted:98Special JudgeDescriptionA group of contestants sits at the round table and plays the following game to relieve anxiety before the start of NEERC 2007. The game is played with a single token that is given to one person at the beginning of the game. This person passes the token to the adjacent person on the left-hand side or to the adjacent person on the right-hand side with a certain probability. A person who receives the token does the same with his own probability and so on. The game ends when each person has received the token at least once. The last person who has received the token wins.The problem is to find the probability of winning for the given person. The probability of passing the token to the left or to the right is individual for each person and is known in advance before the beginning of the game.Contestants are numbered from 1 tonso that the person number 2 sits to the right of 1, the person number 3 sits to the right of 2, and so on. The person number 1 sits to the right ofn. The game starts with the person whose number is specified in the input file and your task is to find the probability of winning for the person numbern.Picture shows 7 contestants at the table with the token given to the person number 3.InputThe first line of the input file contains two integer numbersnandk(2 n 50, 1 kn).ndenotes the total number of contestants,kdenotes the number of the person who has the token at the beginning of the game.The second line of the input file containsn 1 numbers that denote the probabilitiespi(0.01 pi 0.99) of passing the token to the right for the persons numbered from 1 ton 1. The probability of passing the token to the left for the person numberiis 1 pi. The probabilities are given with at most 2 digits after decimal point.OutputWrite to the output file a single number that denotes the probability of winning for the person numbernwith a precision of at least 6 digits after decimal point.Sample Input#17 30.5 0.5 0.5 0.5 0.5 0.5#23 10.3 0.6#324 120.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.5 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01Sample Output#10.1666666667#20.3000000000#30.9800000000HintNote: all probabilities in the third example are on the same line in the actual input file.3642CarpoolTime Limit:2000MSMemory Limit:65536KTotal Submissions:752Accepted:161DescriptionA group of friends has just completed their CS assignments, and because of the nice weather, they decide to go to Joes house for a BBQ. Unfortunately, after all that coding, they are too tired to walk. Fortunately, between them they have enough cars to take everyone.Joe remembers that he needs to stop off at the supermarket along the way to buy some burgers and pop.Jenn proposes that they stop at her house to get a frisbee.Jim decide