Queueing | Topcoder Archive

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 ints len1, len2, p1, and p2. Compute the probability that standing in the first line is a strictly better choice than standing in the second line. More precisely, compute the probability that the last person currently standing in the first line will finish checking out strictly before the last person in the second line is done.

Definition

Class:: Queueing
Method:: probFirst
Parameters:: int, int, int, int
Returns:: double
Method signature:: double probFirst(int len1, int len2, int p1, int p2)
(be sure your method is public)

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.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.