Problem Statement
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 maxR*maxG*maxB possible colors.
Arthur likes random patterns. Therefore he has devised the following randomized method of coloring the fence:
- In the first step he colors plank 0 using the color with components startR, startG, startB.
- 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.
Given
Definition
- Class:
- RandomColoring
- Method:
- getProbability
- Parameters:
- int, int, int, int, int, int, int, int, int
- Returns:
- double
- Method signature:
- double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
- (be sure your method is public)
Notes
- Your return value must have an absolute or relative error less than 1e-9.
- It is given that there exists at least one color that makes a good transition from the color (startR, startG, startB). Using this fact it can be proven that during the coloring process it is impossible to reach a state where there is no color that makes a good transition from the current plank's color. I.e. the coloring process cannot stop before coloring all the planks.
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).
Examples
2
5
1
1
2
0
0
0
1
Returns: 0.0
In this 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.
3
5
1
1
2
0
0
0
1
Returns: 0.22222222222222227
Only the R component can change here. There are nine ways how to color the planks 0, 1, and 2: (2, 0, 0) - (1, 0, 0) - (0, 0, 0) (2, 0, 0) - (1, 0, 0) - (1, 0, 0) (2, 0, 0) - (1, 0, 0) - (2, 0, 0) (2, 0, 0) - (2, 0, 0) - (1, 0, 0) (2, 0, 0) - (2, 0, 0) - (2, 0, 0) (2, 0, 0) - (2, 0, 0) - (3, 0, 0) (2, 0, 0) - (3, 0, 0) - (2, 0, 0) (2, 0, 0) - (3, 0, 0) - (3, 0, 0) (2, 0, 0) - (3, 0, 0) - (4, 0, 0) 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.
7
4
2
2
0
0
0
3
3
Returns: 1.0
As the number of planks is odd, Arthur will certainly have an ugly fence.
10
7
8
9
1
2
3
0
10
Returns: 0.0
For any pair of colors the transition between them is good. The fence cannot be ugly.
10
7
8
9
1
2
3
4
10
Returns: 0.37826245943967396
3
3
2
2
1
0
0
1
2
Returns: 0.09090909090909148
40
50
50
50
0
0
0
0
50
Returns: 0.0
40
50
50
50
49
0
0
1
50
Returns: 7.999999162722319E-6
40
50
50
50
0
49
0
2
50
Returns: 6.400528043573172E-5
40
50
50
50
0
0
49
3
20
Returns: 0.9363916743415929
40
50
50
50
49
0
49
5
15
Returns: 0.9768976795402184
40
50
50
50
49
49
49
10
10
Returns: 0.9980932537435082
40
50
50
50
3
4
5
0
50
Returns: 0.0
40
50
50
50
2
6
4
1
50
Returns: 7.999999162605608E-6
40
50
50
50
45
3
47
2
50
Returns: 2.1599815802982012E-4
40
50
50
50
45
44
7
3
20
Returns: 0.8494042621591069
40
50
50
50
3
1
40
10
10
Returns: 0.995285899775498
40
50
50
50
46
5
48
5
15
Returns: 0.9565504879695093
40
50
50
50
25
25
25
0
50
Returns: 0.0
40
50
50
50
24
25
25
1
50
Returns: 7.999999162595684E-6
40
50
50
50
25
24
25
2
50
Returns: 2.159981580300001E-4
40
50
50
50
25
25
24
3
20
Returns: 0.333577561703687
40
50
50
50
24
24
24
10
10
Returns: 0.97034000737779
40
50
50
50
24
25
24
5
15
Returns: 0.6548209778221126
40
50
50
50
43
18
34
0
0
Returns: 0.0
40
50
50
50
16
7
24
1
1
Returns: 0.9885711963807836
40
50
50
50
36
47
22
0
1
Returns: 0.979045695376202
2
1
1
1
0
0
0
0
0
Returns: 0.0
2
1
1
1
0
0
0
0
50
Returns: 0.0
39
1
1
1
0
0
0
0
0
Returns: 0.0
39
1
1
1
0
0
0
0
50
Returns: 0.0
4
6
9
7
5
7
1
3
6
Returns: 0.21716864069381273
2
5
7
10
1
3
2
3
9
Returns: 0.0
6
9
10
6
3
1
3
3
8
Returns: 0.1801907458222012
39
10
8
7
7
6
6
6
10
Returns: 0.47441441587022387
37
10
10
8
5
6
2
2
5
Returns: 0.12399421390469781
40
8
10
10
2
4
2
2
6
Returns: 0.120270912547511
9
22
27
22
4
1
1
9
19
Returns: 0.34076526666192497
8
27
21
21
16
4
15
12
12
Returns: 0.9075600949313886
4
27
20
28
13
11
12
13
18
Returns: 0.779708917067499
38
30
28
28
17
17
27
2
11
Returns: 0.7206614061190684
39
29
29
22
20
8
6
8
15
Returns: 0.44663445031649157
38
28
23
25
14
11
0
6
19
Returns: 0.23443037657967256
7
45
48
41
2
19
36
12
34
Returns: 0.26122377825213083
2
49
44
47
14
26
9
17
35
Returns: 0.0
9
46
42
50
29
34
21
25
33
Returns: 0.6312973156846686
40
47
40
43
28
22
32
4
34
Returns: 0.0048251635344675175
37
45
49
48
17
28
3
35
48
Returns: 0.7057262782124958
38
50
41
49
3
25
6
3
28
Returns: 0.4998560722744719
37
39
10
26
37
5
2
2
20
Returns: 0.4793340980108003
29
32
42
29
0
22
8
7
29
Returns: 0.0940748277795792
33
48
16
8
37
11
3
32
42
Returns: 1.0
4
8
13
23
1
1
8
2
38
Returns: 0.011294159346762232
13
20
41
24
18
15
2
24
49
Returns: 1.0
20
7
44
34
2
14
23
5
35
Returns: 0.056017040270617054
31
34
16
29
0
7
5
7
18
Returns: 0.5616457008826885
11
32
43
22
14
2
14
20
48
Returns: 0.5230643752132742
39
1
1
31
0
0
27
13
48
Returns: 0.5510884607734773
31
17
17
33
7
7
8
19
46
Returns: 1.0
38
44
4
2
22
1
0
1
2
Returns: 0.7819124360920724
37
50
2
2
20
1
1
2
4
Returns: 0.8556765905194399
32
42
3
2
26
2
0
10
11
Returns: 0.7200588083436756
10
46
5
3
15
2
2
8
21
Returns: 0.49484576859152135
11
5
49
4
2
31
0
3
10
Returns: 0.5560094417114855
39
2
44
3
0
1
2
1
10
Returns: 0.7564387154201265
4
3
4
43
2
2
42
8
23
Returns: 0.4105061129503091
9
4
3
47
2
2
5
2
4
Returns: 0.5011774955495318
35
42
41
3
40
2
1
2
5
Returns: 0.9450650637615796
27
42
44
2
3
21
1
1
6
Returns: 0.8910292041516622
36
41
2
49
25
1
23
5
18
Returns: 0.33994141933106703
35
47
5
40
4
2
8
10
28
Returns: 0.42901950565339647
23
3
50
40
2
1
12
0
6
Returns: 0.8772500538648544
32
3
45
45
2
40
32
6
7
Returns: 0.9601039433165297
39
50
1
1
49
0
0
3
7
Returns: 0.89708294553082
13
50
1
1
49
0
0
17
34
Returns: 0.689947154665351
40
1
50
1
0
33
0
2
22
Returns: 0.24060150375511846
7
1
50
1
0
5
0
5
6
Returns: 1.0
39
1
1
50
0
0
0
9
9
Returns: 1.0
18
1
1
50
0
0
26
20
24
Returns: 0.5752870149251663
14
49
50
1
13
31
0
1
6
Returns: 0.8251230244691329
39
50
49
1
1
44
0
3
40
Returns: 0.21671634944464319
37
49
1
48
25
0
46
0
2
Returns: 0.9288381880358486
5
47
1
50
0
0
0
8
13
Returns: 0.874308849723263
36
1
50
49
0
26
23
1
3
Returns: 0.9484020123432241
39
1
47
48
0
46
46
45
50
Returns: 0.6049551880045907
40
50
50
50
12
19
18
3
5
Returns: 0.9790095941710725
40
50
50
50
12
18
19
3
5
Returns: 0.9790095941710683
40
50
50
50
12
19
19
3
5
Returns: 0.9795736307204372
40
50
50
50
12
19
18
3
6
Returns: 0.9690738249292322
6
2
2
2
0
1
1
1
1
Returns: 0.12494793835901716
25
2
2
2
1
0
1
1
1
Returns: 0.125
38
2
2
2
1
1
0
1
1
Returns: 0.125
39
2
2
2
0
1
1
0
1
Returns: 0.0
6
2
2
2
1
0
1
0
1
Returns: 0.0
25
2
2
2
1
1
0
0
1
Returns: 0.0
40
49
48
47
20
21
22
18
28
Returns: 0.459691946914971
40
40
45
50
0
0
1
20
50
Returns: 0.09671826641877793
40
50
50
50
13
15
17
20
50
Returns: 0.32085447457047506
40
50
50
50
26
25
26
10
50
Returns: 0.054061788408335
40
50
50
50
20
21
22
20
50
Returns: 0.4385170347665593
40
50
50
50
1
1
1
10
20
Returns: 0.9294944930812589
40
50
50
50
23
18
0
8
47
Returns: 0.053615963891243235
40
50
49
47
20
20
20
10
30
Returns: 0.08605175358662734
40
50
50
50
0
0
0
2
50
Returns: 6.400528203524865E-5
40
50
50
50
1
1
1
30
50
Returns: 0.1996885313013972
40
49
49
49
0
0
0
25
26
Returns: 0.9616325712418037
40
50
48
49
49
0
35
12
24
Returns: 0.8037869330085015
39
50
50
50
31
49
23
1
49
Returns: 7.999999162722319E-6
40
50
50
50
1
0
0
3
40
Returns: 0.41028449825339086