시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 1 | 1 | 1 | 100.000% |
The mysterious owner of an electronics factory has decided to do something very intriguing. She has hidden golden transistors inside seven electronic devices, and the people who buy those devices will be invited to a magical, marvelous tour of the factory.
Arnar and Solveig have received a tip that there is a golden transistor hidden inside one device in their local electronics store. First they pooled their money together and bought all the devices, then placed them in a straight line, numbering the devices 0 to N-1. Each device has some number of transistors in it. Then they agreed on a strategy to decide who gets the golden transistor:
First, Arnar will select a range [a, b] (inclusive) of the devices, where 0 ≤ a ≤ b < N. Next, Solveig will choose which one set of devices she wants to take:
Once Solveig has chosen one of the sets of devices, Arnar takes all the devices she did not take.
For example, if there are 3 devices and Arnar selects the range [1, 1], Solveig may choose to take the range [0, 0], the range [1, 1] or the range [2, 2]. On the other hand, if Arnar selects the range [1, 2], then Solveig may choose to take the range [0, 0] or the range [1, 2].
Given how many transistors are in each device, and that Arnar and Solveig will each try to maximize their probability of getting the golden transistor (which is maximized by taking electronics with the maximum number of transistors), what is Arnar's probability of getting the golden transistor and thus winning the magical, marvelous tour?
The first line of the input gives the number of test cases, T. T lines follow. Each line contains five numbers: N, p, q, r and s. This indicates that there are N devices, and the ith device contains ((i * p + q) MOD r + s) transistors. Remember that the devices are numbered from 0 to N-1.
Limits
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is Arnar's probability of winning the magical, marvelous tour.
y will be considered correct if it is within an absolute or relative error of 10-9 of the correct answer.
8 1 1 1 1 1 10 17 1 7 1 2 100 100 200 1 20 17 3 23 100 10 999999 999999 1000000 1000000 2 1 1 1 1 3 1 99 100 1 999999 1000000 999999 1000000 1000000
Case #1: 0.0000000000 Case #2: 0.6111111111 Case #3: 0.0098039216 Case #4: 0.6471920290 Case #5: 0.6000006000 Case #6: 0.5000000000 Case #7: 0.0291262136 Case #8: 0.6666666667
Note that the last sample case does not meet the limits for the Small dataset. You could have a correct solution for the Small dataset that returns the wrong answer, or runs for a very long time, on the last sample case.
Explanation of Sample Cases
In the first sample case, there is one electronic device with one transistor. Arnar must select the range [0, 0], and Solveig must choose to take all the devices in the range [0, 0]. Arnar can't possibly win the magical, marvelous tour.
In the second sample case, there are ten electronic devices, with the following numbers of transistors: [2, 5, 1, 4, 7, 3, 6, 2, 5, 1]. Arnar will choose the range [4, 5], which contains the devices with 7 and 3 transistors. Solveig will choose the range [6, 9], which contains the devices with 6, 2, 5 and 1 transistors, leaving Arnar with the first six devices, and a probability of 22/36 of winning the tour.
In the third sample case, the devices have 101 and 1 transistors.
In the fourth sample case, the devices have the following numbers of transistors: [103, 120, 114, 108, 102, 119, 113, 107, 101, 118, 112, 106, 100, 117, 111, 105, 122, 116, 110, 104].
In the fifth sample case, the devices have the following numbers of transistors: [1999999, 1999998, 1999997, 1999996, 1999995, 1999994, 1999993, 1999992, 1999991, 1999990].
In the sixth sample case, the devices both have 1 transistor.
In the seventh sample case, the devices have the following numbers of transistors: [100, 1, 2].
Contest > Google > Code Jam > Google Code Jam 2014 > Round 3 A2번