WaitingForBusAgain | Topcoder Archive

Problem Statement

You are waiting at a bus station.

There are n buses. Each of them stops at this station at regular intervals. You know the length of the interval for each bus, but you have no idea when the bus started running, so you do not know the offset.

Formally, you are given a int[] f with n elements. For each valid index i, there is a bus labeled i which comes to your bus stop every f[i] minutes. Additionally, for each bus there is some hidden random real number x[i] such that the exact times when the bus arrives at the bus stop have the form x[i] + k*f[i] for all integers k. We assume that each x[i] was chosen uniformly at random from the half-open interval [0, f[i]), and that all x[i] are mutually independent.

You just arrived at this bus stop. What is the expected value of the label of the next bus that will come to the station?

Definition

Class:: WaitingForBusAgain
Method:: expectedBus
Parameters:: int[]
Returns:: double
Method signature:: double expectedBus(int[] f)
(be sure your method is public)

Notes

Your answer will be accepted if your return value has an absolute or a relative error at most 1e-9.

Constraints

f will have between 1 and 1,000 elements, inclusive.
Each element of f will be between 1 and 1,000,000, inclusive.

Examples

```
{8,8,8,8}
```
```
Returns: 1.5
```
The setting is symmetric, so all buses have equal probability to be the next bus that arrives. Thus, the answer is (0+1+2+3) / 4 = 1.5
```
{1,2,3}
```
```
Returns: 0.5
```
```
{3,2,1}
```
```
Returns: 1.5000000000000002
```
The answer is different from case 1 since the buses have different labels. The bus that has the smallest period now has the biggest label.

{3,1,4,1,5,9,2,6,5,3,5}

Returns: 3.7044469870664325

{26, 19548, 19299, 19431, 39568, 19476, 19726, 19530, 19613,
19529, 19679, 19552, 19706, 19505, 19666, 19349, 19755, 19424,
19486, 19596, 19439, 19500, 19639, 19520, 19472, 19675, 19602,
19552, 19933, 19424, 19316, 19497, 19582, 19531, 19679, 19742,
19896, 19365, 20083, 19542, 19827, 19583, 19592, 19593, 19661,
19340, 19403, 19664, 19690, 19655, 19727, 19661, 19528, 19836,
19819, 19414, 19770, 19500, 19653, 19613, 19579, 19794, 19668,
19729, 19428, 19477, 19733, 19641, 19680, 19594, 19667, 19878,
19571, 19627, 19576, 19422, 19521, 19512, 19481, 19620, 19364,
19487, 19740, 19627, 19795, 19353, 19251, 19865, 19710, 19597,
19610, 19710, 19491, 19598, 19650, 19828, 19726, 19810, 19766,
19692}

Returns: 3.1415926535671885

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.