PinballLanes
SRM 132 · 2003-02-01 · by lars2520
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.
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.
{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
Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PinballLanes with a public method int getProb(vector<int> probs, int times) · 117 test cases · 2 s / 256 MB per case