《iee极限编程预赛题目》由会员分享，可在线阅读，更多相关《iee极限编程预赛题目（21页珍藏版）》请在金锄头文库上搜索。
1、Language:1246Hilbert Curve IntersectionsTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 171 Accepted: 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,
2、. 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). Hn is defined recursively in terms of Hn-1, for n = 2, 3, . by four transformations: 1.Halve al
3、l 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,
4、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
5、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
6、 form n x1 x2 y which represents Hn and 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 Hn with the segment. Caution: A brut
7、e 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 200237
8、66Hexagon Coin TossTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 378 Accepted: 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 t
9、he 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 contai
10、ns 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). Here N representing the number of hexagons in the longest row. M representing the number of rows and K shows the number of hexagon
11、s 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
12、 line of each case contains three integers N, M, K, representing the size of the chessboard. N and M will be in the range of 1，1000 and K equals either N or N-1. It is guaranteed that all input information is valid (So that (2, 1, 1) will not appear).The following line is a real number R, the radius
13、 of the coin.Input is ended with a case of N=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
14、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.Proba
15、bility 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: 1000MS Memory Limit: 10000KTotal Submissions: 6
16、32 Accepted: 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 f
