2010ACM程序设计亚洲域哈尔滨初赛试题.doc

DescriptionIn our high school, we had learn a theorem: if two numbers have the invariablenes sum, they will get the maximum product when they are equal, on the side, another is if two numbers have the invariablenes product, they will get the minimum sum when each of them equals the other one.Now, I will give you a same equations, you should give me the result that you can get from the above theorems.InputThere are several test cases. Each case contains a string, it is an equation, and its length is less than 1024. In the equation, the variants are different, and only contain lower letters, the number is a legality double number variants , operator sign and number are separate by spaces.OutputOutput the result that you can get from the two theorems(the result is rounded to two decimal digits). And the result should express as ranges, ranges will be united by letter U, each range have a left value and a right value and the range should begin with ( and end with ), if the value is infinite it should be replace with inf, all numbers, signs, values should separate by space.Sample Inputx + y = -4.00a * b = 4.0401s * t = -0.000i * j = 0.01Sample Output(-inf x * y = 4.00)(-inf a + b = -4.02) U (4.02 = a + b +inf)(-inf s + t +inf)(-inf i + j = -0.20) U (0.20 = i + j +inf)DescriptionOne day， XiaoA is calculating an upright expression(A is not zero):ABCD*) 9-DCBAHe found the answer is ABCD=1089, and then, he think about a hard question (it is below), what is the answer?ABCDEFGH.RST*) X-TSR.HGFEDCBAInputThere are several test cases. Each case contains two integer L and X, L indicates the length of the variant above and X is the value of the factor (0L=1024, 0=X=9).OutputYou should output the solution for the upright expression, if there is more than one solution, you should output the minimum solution, and if there is not solution, you should output No solutionSample Input4 96 53 1Sample Output1089No solution101HintThe different letters can indicate same number.DescriptionWe define that if Integer X and N satisfy that : X*X = N (X+1)*(X+1), X can be called as the root of N. Now, I give you a integer N, you should tell me what is the root of it, and the result is binary digits.InputThere are several test cases, each case contains an Integer N(0=N=10200)# indicates the end of input.OutputOutput the root of input in binary digits.Sample Input456100#Sample Output1010101010DescriptionHank was potty about Rubiks cube; Rubiks cube is an intelligence toy. Hank spent hours each day exercising, so the Rubiks cube breaks frequently. Hank had to buy new Rubiks cube often.Today, hank buys a new Rubiks cube, and it is chaotic. Can you help him to find the colors in opposite faces?InputThere are several test cases; the first integer T indicates the number of test cases. Each case includes an integer N and six blocks, N indicates the rank of the Rubiks cube(1=N=11), and the six blocks indicate the colors of the six faces of the Rubiks cube.OutputOutput the case number and the pairs of colors in order of B, G, O, R, W, Y, like this:B-opposite-face-colorG-opposite-face-colorO-opposite-face-colorR-opposite-face-colorW-opposite-face-colorY-opposite-face-colorAfter each case there is a blank line.Sample Input12YYYYOOOOBBBBRRRRGGGGWWWWSample OutputCase #1:B-GG-BO-RR-OW-YY-WDescriptionXiaoz teacher gives him a very hard problem. Teacher gives him two strings S, T, and asks xiaz judge that if string S is a substring in string T, xiaoz is exultingly, because The KMP algorithm is suitable, but then teacher says, if string T has a substring which can become string S by edit some characters, it is also accept. This problem makes xiaoz be headache, so he ask for your help.InputThere are several test cases. In each case, the first line contains an integer k(K=100), indicate themaximumtimes you can edit with string T. Then the second line contains a string, indicate string S, and the third line contains a string, indicate string T. Both of lengths of the strings will be less than 10010.OutputIf the string S can be the substring of string T by editing string T andno more than Ktimes then print YES! else print NO!.Sample Input2annualannealingSample OutputYES!DescriptionGeometry transformation is a widely used technology in computer graphics. The problem you need to solve today is to compute the area of the cubic projection. Refer to the following Fig.1, the projection of the cube on face xoy is shown as the grey area on xoy.Fig.1 A simple example of projectionIn graphical processing, rotation around a line is a foundational operation. Fig.2 gives an example. In Fig.2, the right cube is obtained by rotating the left cube counterclockwise around vector L by 180 degrees.Fig.2 A rotation exampleGive a cube C, a vector L and an angle A, your job is to calculate the area of the projection of C on face xoy after rotating cube C counterclockwise around vector L by angle A degree. The cubes are always given with edge w parallel to x-axis, edge h parallel to y-axis and edge l parallel to z-axis, same as Fig.1. So a known side length and a known coordinate of vertex p can determine the cube. Vertex p is the closest vertex to point o.InputWe test the problem in many cases. The first line is the number of test cases. In each case, the side length of the cube and the coordinate of vertex p are give first. Following that is the vector L. vector L is given as the form of start coordinate and the end coordinate. Finally, the angle A is presented. All the numbers given are integers and are in interval -10000, 10000.OutputThe output consists of the areas of all the projection. The results must be round to 2 decimal numbers.Sample Input2205 5 50 15 15 -15 15 15315100 0 00 0 0 10 10 10275Sample Output565.69148.80DescriptionNowadays, the society is developed economy, and consumes a lot of resources, especially the oil.Now, some pipes transport oil from city A to city B for the consuming of city B, but the distance from city A to city B is too long, there are many transfer stations, and K levels among the transfer stations, city A and city B, city A is level 1, and city B is level K, and the levels of transfer stations are between 2 and k-1, and only the transfer stations which has consecutive levels can be connected.We know all the volumes of the pipes, the citymaster of city B employs builders to expand some pipes, avoid the leavings in pipes, but the builders hope the less expandedness the better, achieve the require of the citymaster of city B minimally.The citymaster of city B want know the values of the flow before and after the expansion.In figure, the values of the flow before and after the expansion is 2 and 4.Inp