Little Arthur has built a new fence around his house and now it is time to color it.
The fence consists of N planks numbered 0 to N-1 such that i-th plank is adjacent to planks i-1 and i+1 (modulo N) for all i between 0 and N-1, inclusive.
Each of the planks in the fence has to be colored using a single color. Different planks may have different colors. Each color is defined by three integer components: R, G, and B (meaning red, green, and blue, respectively), where 0 ≤ R < maxR, 0 ≤ G < maxG, and 0 ≤ B < maxB. Arthur can use any of the maxRmaxGmaxB possible colors.
Arthur likes random patterns. Therefore he has devised the following randomized method of coloring the fence:
1. In the first step he colors plank 0 using the color with components startR, startG, startB.
2. Next, for each i from 1 to N-1, in this order, he does the following: He looks at the (already determined) color C of the plank (i-1). The color for plank i is chosen uniformly at random among all colors that make a good transition from the color C. (Good transitions are defined below.)
A transition from color (R, G, B) to color (R', G', B') is called good if all components differ by at most d2 units (formally, |R - R'| ≤ d2, |G - G'| ≤ d2, |B - B'| ≤ d2) and at least one component differs by at least d1 units (formally, at least one of the conditions |R - R'| ≥ d1, |G - G'| ≥ d1, |B - B'| ≥ d1 holds). Intuitively, a transition between two colors is called good if they are neither too similar, nor too different.
Unfortunately, Arthur hasn't realized that after coloring all planks the transition from plank (N-1) to plank 0 does not have to be good. (Note that the fence is cyclic and thus these two planks are adjacent.) If that happens, the fence will look ugly.
There are at most 120 test cases. Test cases end with EOF.
For each test case,giving nine integers N, maxR, maxG, maxB, startR, startG, startB, d1, and d2.
Constraints
- N will be between 2 and 40, inclusive.
- maxR, maxG, maxB, will be between 1 and 50, inclusive.
- startR will be between 0 and maxR-1, inclusive.
- startG will be between 0 and maxG-1, inclusive.
- startB will be between 0 and maxB-1, inclusive.
- d1 and d2 will be between 0 and 50, inclusive.
- d1 will be less than or equal to d2.
- It is guaranteed that there will exist at least one valid color that makes a good transition from color (startR, startG, startB).
For each test cases, print one real number in one line indicating the probability that the fence will be ugly. (I.e., the probability that the transition from the color of plank (N-1) to the color of plank 0 is not good.)
2 5 1 1 2 0 0 0 1 3 5 1 1 2 0 0 0 1 7 4 2 2 0 0 0 3 3
0.0 0.22222222222222227 1.0
In first test case, there are only two planks. Plank 1 will surely be colored using a color that makes a good transition from the color of plank 0. By symmetry, the transition from plank 1 color to plank 0 color has to be good as well. The fence will never be ugly.
In second test case, all of these ways are equally likely. In two of them the transition from the color of plank 2 to the color of plank 0 is not good. Thus the probability of having an ugly fence is 2/9.
In third test case, as the number of planks is odd, Arthur will certainly have an ugly fence.
Info: 本題輸出為浮點數，絕對或相對誤差 1e-6 以下視為正確
Migrated from old NTUJ.
SRM540 div1.500
| No. | Testdata Range | Score |
|---|