RandomizedParking
SRM 852 · 2024-01-23 · by misof
Problem Statement
There is an underground parking lot. A single long cyclic road weaves its way through the entire parking lot. To prevent collisions, the entire road is one-way.
Along the road there are N parking spots, numbered from 0 to N-1 in driving order. (I.e., if you are at the spot x and you drive forward, the next spot you'll reach will be (x+1) modulo N.)
You are given the current state of all parking spots in the
There are N entrances into the parking lot: one between each pair of consecutive parking spots.
In the future, some additional cars will enter the parking lot. These cars will appear one at a time, and each car will park before the next one enters. The entrance used by each car will be chosen uniformly at random, and these choices are all mutually independent.
A parking car always drives along the cyclic road until it finds and takes the first available parking spot.
You are given an
Notes
- Your return value may have an absolute or a relative error at most 1e-9.
Constraints
- start will have between 3 and 20 characters, inclusive.
- Each character in start will be 'X' or '.'.
- At least one character in start will be a period.
- K will be between 1 and the number of periods in start, inclusive.
"....." 1 Returns: 0.0
The first car to enter this empty parking lot will park on the first available spot.
"X.X.X.X." 1 Returns: 0.5
The first car that enters this parking lot will either find a parking spot immediately, or it will find an occupied parking spot followed by a free one. Each happens with probability 4/8 = 0.5. Thus, the expected number of occupied spots encountered by the next car will be 0.5 * 0 + 0.5 * 1 = 0.5.
"X.X..XX." 4 Returns: 3.5
The fourth car that enters this parking lot will be the last one. Regardless of what happened before, at that moment there will be exactly one free parking spot. The car will be equally likely to encounter 0, 1, 2, ..., 7 taken spots before getting to the free one.
"......." 2 Returns: 0.14285714285714285
With probability 1/7 the second car will use the same entrance as the first car. If that happens, it will have to drive past the first car before it gets to a free parking spot.
"X.X....X" 2 Returns: 0.921875
The first car will park in spot 1 with probability 3/8. (This happens if it enters the cycle before spot 7, before spot 0, or before spot 1.) It will park in spot 3 with probability 1/4, and in each of the spots 4, 5, 6 with probability 1/8. (Note that direction of driving matters. If we had this starting parking lot but the cars drove in the opposite direction, the final answer would not be the same.)
Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomizedParking with a public method double solve(string start, int K) · 23 test cases · 2 s / 256 MB per case