Problem Statement
An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.
The robot's path is considered simple if it never visits the same point more than once. (The robot's starting point is always the first visited point.) Return a double containing the probability that the robot's path is simple. For example, "EENE" and "ENW" are simple, but "ENWS" and "WWWWSNE" are not ('E', 'W', 'N' and 'S' represent east, west, north and south, respectively).
Definition
- Class:
- CrazyBot
- Method:
- getProbability
- Parameters:
- int, int, int, int, int
- Returns:
- double
- Method signature:
- double getProbability(int n, int east, int west, int south, int north)
- (be sure your method is public)
Notes
- Your return must have relative or absolute error less than 1E-9.
Constraints
- n will be between 1 and 14, inclusive.
- east will be between 0 and 100, inclusive.
- west will be between 0 and 100, inclusive.
- south will be between 0 and 100, inclusive.
- north will be between 0 and 100, inclusive.
- The sum of east, west, south and north will be 100.
Examples
1
25
25
25
25
Returns: 1.0
The robot only takes one step, so it never visits a point more than once.
2
25
25
25
25
Returns: 0.75
The robot will visit its starting point twice only if the two moves are in opposite directions.
7
50
0
0
50
Returns: 1.0
Here, the only possible directions are north and east, so the robot will never visit the same point twice.
14
50
50
0
0
Returns: 1.220703125E-4
Here, the only possible directions are east and west. The only two available paths are "EEEEEEEEEEEEEE" and "WWWWWWWWWWWWWW". The probability is equal to 2 / (2^14).
14
25
25
25
25
Returns: 0.008845493197441101
The probability is quite small for n=14.
7
4
75
13
8
Returns: 0.6757631663232042
11
37
23
15
25
Returns: 0.0428254853475433
1
23
35
39
3
Returns: 1.0
2
89
1
10
0
Returns: 0.9822
7
50
2
26
22
Returns: 0.454360187891202
13
100
0
0
0
Returns: 1.0
6
54
3
9
34
Returns: 0.6494356190800041
11
63
12
16
9
Returns: 0.19706951917799853
6
21
29
34
16
Returns: 0.2401067696180005
6
0
46
16
38
Returns: 0.5705340927999994
6
0
62
29
9
Returns: 0.7884079895619984
1
10
36
35
19
Returns: 1.0
13
11
50
18
21
Returns: 0.09395670096829466
1
6
33
15
46
Returns: 1.0
2
12
11
21
56
Returns: 0.7384000000000002
4
15
26
46
13
Returns: 0.5199380800000001
14
100
0
0
0
Returns: 1.0
14
36
30
21
13
Returns: 0.008999903530642655
7
41
21
1
37
Returns: 0.35289473865212256
6
25
64
9
2
Returns: 0.20384536274
5
0
77
4
19
Returns: 0.9448662255999989
8
10
22
35
33
Returns: 0.08918977597712467
4
8
5
72
15
Returns: 0.5403199999999999
3
25
19
20
36
Returns: 0.5832200000000002
10
4
43
16
37
Returns: 0.2577111504854486
9
4
58
8
30
Returns: 0.5079240227065852
11
27
4
31
38
Returns: 0.05748275503085238
14
100
0
0
0
Returns: 1.0
6
2
4
41
53
Returns: 0.06725567844200002
13
21
31
31
17
Returns: 0.024470155173989958
3
22
5
26
47
Returns: 0.5593760000000003
6
0
13
50
37
Returns: 0.12533415249999993
3
4
19
49
28
Returns: 0.528192
13
58
37
0
5
Returns: 0.003400084892285699
10
67
5
17
11
Returns: 0.44260382597029324
6
28
26
9
37
Returns: 0.2951868933220003
3
9
33
36
22
Returns: 0.6228100000000001
4
61
15
24
0
Returns: 0.6068244999999998
12
100
0
0
0
Returns: 1.0
13
23
62
0
15
Returns: 0.047035025335926316
5
26
8
5
61
Returns: 0.6861699321999993
1
10
1
41
48
Returns: 1.0
14
34
4
29
33
Returns: 0.04681301459156854
1
56
1
21
22
Returns: 1.0
10
16
19
51
14
Returns: 0.14021992625106874
1
83
14
2
1
Returns: 1.0
2
20
33
28
19
Returns: 0.7616000000000002
13
1
3
48
48
Returns: 7.225725260960254E-4
2
9
28
39
24
Returns: 0.7624000000000001
8
100
0
0
0
Returns: 1.0
14
37
41
10
12
Returns: 0.0037585703186666587
8
25
25
25
25
Returns: 0.09027099609375
13
17
21
29
33
Returns: 0.012345865520426241
14
1
33
27
39
Returns: 0.06020597941544461
13
34
27
21
18
Returns: 0.013347502999658369
12
21
29
33
17
Returns: 0.035003062789088504
14
24
26
25
25
Returns: 0.00894758399699008
14
15
29
11
45
Returns: 0.07310142245213239
14
1
50
49
0
Returns: 0.9042036545846861
14
83
15
1
1
Returns: 0.10348592504116648
14
35
15
37
13
Returns: 0.05066297972477722
13
21
14
30
35
Returns: 0.012741423828043255
14
24
26
26
24
Returns: 0.009050148087856178
14
36
14
39
11
Returns: 0.07132241978952752
14
24
23
22
31
Returns: 0.010881498898316704
14
23
27
25
25
Returns: 0.009256729591737187
14
1
2
3
94
Returns: 0.6506631549535102
13
25
25
25
25
Returns: 0.013135373592376709
13
33
42
16
9
Returns: 0.009587275568806024
14
10
23
27
40
Returns: 0.014926355429481371
13
12
1
50
37
Returns: 0.006518487218398356
14
11
63
1
25
Returns: 0.22529858193679217
14
15
20
35
30
Returns: 0.008023689596037983
14
12
27
30
31
Returns: 0.014371198979525563
14
97
1
1
1
Returns: 0.8668361312058556
14
12
63
1
24
Returns: 0.195292532586908
14
1
49
25
25
Returns: 0.18693152905571658
14
26
21
18
35
Returns: 0.018033342774776768
14
1
1
1
97
Returns: 0.8668361312013636
14
44
7
23
26
Returns: 0.07951614141334706
13
8
18
62
12
Returns: 0.14687508919248357
14
10
20
30
40
Returns: 0.009919275575684559