Queueing
SRM 687 · 2016-04-01 · by lg5293
Problem Statement
You have just finished shopping at a supermarket and you are heading to the checkout. There are two lines available. The first line currently has len1 people, while the second line has len2 people. In each line, the cashier is just going to start checking out the first person.
The time to check out a person depends on the cashier's experience. For each pair of positive integers (p,k): the probability that a cashier with experience p will take exactly k seconds to check out any single person is given by the formula ((1/p) * (1 - 1/p)^(k-1)). The cashier in the first line has experience p1, and the cashier in the second line has experience p2.
You are given the
Notes
- Your return value must have absolute or relative error less than 1e-9.
- When evaluating the formula, assume that 0^0 = 1. Hence, the probability that a cashier with experience 1 checks out a person in 1 second is 1 * 0^0 = 1.
Constraints
- len1,len2,p1,p2 will be between 1 and 1,000, inclusive.
1 2 2 1 Returns: 0.5
There are two lines. The first line has one person, the second line has two people. The first cashier has experience 2, and the second cashier has experience 1. The cashier with experience 1 will process each customer in exactly 1 second. So, we want to know the probability that the first cashier can finish processing the only customer in 1 second. This happens with probability 0.5.
1 3 3 7 Returns: 0.9835390946502058
3 1 7 3 Returns: 0.010973936899862834
12 34 56 78 Returns: 0.999996203228025
3 6 8 4 Returns: 0.5229465300297028
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 Queueing with a public method double probFirst(int len1, int len2, int p1, int p2) · 117 test cases · 2 s / 256 MB per case