Problem Statement
In many pinball games there are a number of lanes, each of which has a lightbulb under it. Every time the pinball rolls through one of the lanes, the light's state toggles (if it's on, it turns off, and vice versa). Generally, if you can get all of the lights to be on simultaneously, then you get some points, and the lights will all immediately reset to off.
In this problem, we will be considering the scenario where the lanes are all lined up next to each other, something like this, where 'L' represents a lightbulb:
| | | | | | L | L | L | L | ... | | | | |
The pinball surface is at an angle so that, once the ball rolls up one of the lanes, gravity will pull it back down through a lane (though not necessarily the same one). The lane that it rolls back down is somewhat random, but the ball is probably more likely to roll down lanes closer to the one that it came up, than lanes further away from the one it came up (though this is not always true, and the exact probabilities are dictated by the input).
Your task is to determine the expected number of times that all of the lights will be on, given the number of times that the ball rolls up some lane and then back down, and assuming that all of the lights are initially off. You will be given a
For example, if probs = {3,2,1}, there are three lanes:
| | | | | 0 | 1 | 2 | | | | |
If the ball rolls up lane 0, it is 3 times as likely to roll down lane 0 (which is 0 away from lane 0) as it is to roll down lane 2 (which is 2 away from lane 0). Similarly, if it rolls up lane 0, it is twice as likely to roll down lane 1 as it is to roll down lane 2. If the ball rolls up lane 1, then it is 2/3 as likely to roll down lane 0 as it is to roll down lane 1, and 2/3 as likely to roll down lane 2 as it is to roll down lane 1. Since there is no lane that is 2 lanes away from the middle lane, the last element of probs is ignored when the ball rolls up lane 1. In other words, if you rolled it up the middle lane 7 times, you would expect it to roll down lane 0 twice, the lane 1 thrice, and lane 2 twice.
Definition
- Class:
- PinballLanes
- Method:
- getProb
- Parameters:
- int[], int
- Returns:
- int
- Method signature:
- int getProb(int[] probs, int times)
- (be sure your method is public)
Notes
- If all of the lights are turned on after the ball rolls up, but before it rolls back down, that counts as all of the lights being turned on, and the lights reset before the ball rolls back down.
Constraints
- probs will contain between 2 and 8 elements, inclusive.
- Each element of probs will be between 1 and 1000, inclusive.
- times will be between 1 and 1000, inclusive.
- To prevent rounding errors the return value, prior to rounding, will not be within 0.0001 of x + 0.5 for any integer x.
Examples
{1,1}
2
Returns: 1
There are two lanes, and each one has an equal probability of being rolled down, after the ball has rolled up. Each time the ball rolls up, and back down, there are two possible outcomes: 1) The ball rolls down through the same lane it rolled up. 2) The ball rolls down the lane it didn't roll up. Each occurs with equal probability, and each leave the state of the lights as both off (remember, if all the lights are on, they immediately turn off). Thus, for each of the two up and down rollings, the expected number of times that all lights will be lit up is 0.5. 0.5*2 = 1, so the result is 1.
{1,1000}
2
Returns: 2
Here, the ball is 1000 times more likely to roll down the lane that it didn't roll up, so each time the ball rolls up and down, it is almost guaranteed to turn both lights on, at which point they immediately reset to off.
{3,2,1}
10
Returns: 2
The result, prior to rounding is about 1.610
{1,2,4}
3
Returns: 1
{1,2,3,4,5,6,7,8}
1000
Returns: 7
{1,1,1,1,1,1,1,1}
1000
Returns: 6
{1,1000,1000,1000,1000,1000,1000,1000}
892
Returns: 7
{1,100,100,100,100,100,100,100}
892
Returns: 6
{1,1000,1000}
1000
Returns: 250
{1,1,1}
1000
Returns: 200
{1,2,3,2,1}
35
Returns: 2
{1000,1,1,1,1}
1000
Returns: 1
{67,542,433,396,961,108,977}
821
Returns: 11
{350,485,196,811,31,194}
213
Returns: 5
{764,489,537,487,928,233,177}
235
Returns: 3
{650,278,147,337,541,501}
804
Returns: 16
{435,197,761,828}
192
Returns: 18
{302,226,455,788,689,868,333}
314
Returns: 4
{931,650,938,715,126,94,590,18}
791
Returns: 5
{765,464,43,973,864,791}
45
Returns: 1
{163,402,778,959,404,965}
742
Returns: 20
{825,858,874,882}
567
Returns: 54
{588,470,784,758}
238
Returns: 22
{441,906,522,825,768,16,290}
85
Returns: 1
{725,968,236,885,771}
375
Returns: 17
{169,132,983,268,438}
909
Returns: 45
{15,462,636,801,619,900,565}
971
Returns: 13
{115,853,463,686,334,550,862,41}
359
Returns: 3
{526,490,789,883,269,948}
748
Returns: 18
{68,328}
474
Returns: 393
{841,218,706,956,462,784,715,495}
100
Returns: 1
{985,755,639,986,17,821,423,760}
450
Returns: 3
{814,227,731,5,72}
262
Returns: 10
{900,906,334,137,955,611,736}
402
Returns: 5
{107,416}
967
Returns: 769
{321,525,656,483,341}
868
Returns: 43
{411,437,491,506,400,574}
752
Returns: 18
{33,336,347,566,312,201,950}
894
Returns: 12
{999,282,483,197}
983
Returns: 61
{669,967,349,640,456,164}
257
Returns: 6
{369,790,327,647,363}
641
Returns: 31
{951,534,120,783}
455
Returns: 33
{415,719,426}
621
Returns: 132
{550,989,389,78,375,824}
322
Returns: 8
{278,365,183,713,853,569,890}
627
Returns: 8
{882,801,873,148,650,12,549,777}
826
Returns: 5
{173,787,518,4,40,988,611}
1000
Returns: 13
{177,405}
374
Returns: 260
{177,2}
95
Returns: 1
{11,944,31,358,985,418}
594
Returns: 17
{702,227,681,861}
55
Returns: 4
{472,355,62,663,186,100}
6
Returns: 0
{815,668,709,282,933,844,947,21}
154
Returns: 1
{911,358,487,995,398,628,823,459}
850
Returns: 5
{75,229,705,847,8}
694
Returns: 36
{399,670,785,304,726}
385
Returns: 19
{793,476,729}
97
Returns: 18
{327,519,750,164}
261
Returns: 27
{194,57,861,430,767,520,686}
922
Returns: 12
{394,188}
977
Returns: 316
{774,40,464,548}
883
Returns: 50
{991,945,69}
425
Returns: 70
{25,711,777,291}
347
Returns: 42
{562,904,564}
424
Returns: 89
{19,914,212,67,488}
998
Returns: 52
{202,931,286,473,598,486,796}
580
Returns: 8
{577,25,574,475,584,296}
828
Returns: 18
{503,358,885,670,112,235,161,418}
916
Returns: 6
{699,296}
157
Returns: 47
{548,441,446,736,171,957,209}
582
Returns: 7
{851,928,210,554,609,371,243,517}
141
Returns: 1
{609,439,798,423}
668
Returns: 61
{294,476}
434
Returns: 268
{408,269,945,781,539,490,804,276}
295
Returns: 2
{541,866,526,105,472}
543
Returns: 25
{525,372,365,676,759}
444
Returns: 20
{507,286,717,153,710}
634
Returns: 29
{438,900,211}
174
Returns: 35
{613,42,146,327,755,75,80}
685
Returns: 7
{120,982,682,445,64}
105
Returns: 5
{380,978,250}
699
Returns: 148
{920,950,230,93,712}
690
Returns: 29
{93,751,352,292}
896
Returns: 105
{579,499,371,291,814,913,973,872}
336
Returns: 2
{440,651,785,472}
365
Returns: 37
{246,943,695,845,205,406,74}
480
Returns: 6
{569,741,624,610}
197
Returns: 19
{92,981,362,240,400,256}
431
Returns: 12
{322,22,674,330,303,930}
544
Returns: 13
{339,510}
647
Returns: 389
{651,405,81,66,452}
853
Returns: 33
{892,371,724,584}
231
Returns: 18
{452,887,945,149,758,451}
789
Returns: 20
{139,229,84,356,728,358,406,323}
265
Returns: 2
{274,27,624,98,92,452}
508
Returns: 11
{998,424,733,931,626,873,720}
713
Returns: 8
{986,695,802}
984
Returns: 184
{369,732,976,675}
790
Returns: 86
{512,51}
410
Returns: 37
{374,31,398,158,866,410,629}
93
Returns: 1
{446,822,593}
953
Returns: 206
{799,646,899,462,904,473,401}
274
Returns: 3
{921,69,115}
153
Returns: 10
{282,780,301}
399
Returns: 87
{618,292,485,120,426,760,172,314}
913
Returns: 5
{524,420,387,896,424}
45
Returns: 2
{378,401,234,782,371,322,947,234}
531
Returns: 3
{501,889,784,38,297}
414
Returns: 19
{742,186,70,293,876,941}
956
Returns: 17
{263,457,72,568,725,414}
191
Returns: 5
{513,409,606}
642
Returns: 125
{705,257,812,820}
88
Returns: 7
{ 1, 20, 50, 60, 30, 20, 10, 50 }
577
Returns: 4
{ 1, 5, 7, 2, 6, 4, 1, 1 }
1000
Returns: 7
{ 1, 2, 3, 4, 3, 2, 1 }
1000
Returns: 13
{ 12, 3, 2, 1 }
1000
Returns: 45
{ 1000, 437, 187 }
1000
Returns: 143