RoundCountDrawing | Topcoder Archive

Problem Statement

A group of n people are getting ready to play a game, and they will pick a starter using the following method: The n players stand in a circle and are numbered from 0 to n-1 in clockwise order (it doesn't matter where the numbering starts). Then, each player secretly and randomly picks a number between 0 and k, inclusive. Finally, all the chosen numbers are added up to get a number R. Starting at player 0 and going in clockwise order, the players will count from 0 to R. Whoever gets R will be the starter.

You will be given n, k and i and have to return the probability that the participant with number i is picked as starter, assuming each participant chooses his number independently and uniformly between 0 and k, inclusive.

Definition

Class:: RoundCountDrawing
Method:: getProb
Parameters:: int, int, int
Returns:: double
Method signature:: double getProb(int n, int k, int i)
(be sure your method is public)

Notes

Each player chooses his number in a purely random way, without employing any kind of strategy.
The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

n will be between 1 and 1000, inclusive.
k will be between 1 and 1000000000 (109), inclusive.
i will be between 0 and n-1, inclusive.

Examples

```
2
```
```
1
```
```
0
```
```
Returns: 0.5
```
If both players pick the same number (0-0 or 1-1), player 0 gets selected. Otherwise (1-0 and 0-1), player 1 is selected.
```
2
```
```
1
```
```
1
```
```
Returns: 0.5
```
Same scenario as in the previous example.
```
5
```
```
4
```
```
2
```
```
Returns: 0.2
```
As a generalization of the previous scenario, if everybody can choose any number between 0 and n-1, then all players have the same probability (1/n).
```
256
```
```
16
```
```
128
```
```
Returns: 0.0026863846279569195
```

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.