CoinReversing | Topcoder Archive

Problem Statement

You initially have N coins on the table, all with heads up. Given int[] a containing K integers, you first randomly choose a[0] coins and reverse them (from head to tail, or from tail to head), then randomly choose a[1] coins and reverse them, ..., and finally randomly choose a[K-1] coins and reverse them. Calculate and return the expected number of heads after these operations.

Definition

Class:: CoinReversing
Method:: expectedHeads
Parameters:: int, int[]
Returns:: double
Method signature:: double expectedHeads(int N, int[] a)
(be sure your method is public)

Notes

When you choose a specified number (say x) of coins, each combination of x coins has the same probability of being chosen.
The returned value must have an absolute or relative error less than 1e-9.

Constraints

N will be between 1 and 1000, inclusive.
a will contain between 1 and 50 elements, inclusive.
Each element in a will be between 1 and N, inclusive.

Examples

```
3
```
```
{2,2}
```
```
Returns: 1.6666666666666667
```
You first reverse 2 coins from heads to tails. Then you randomly choose 2 coins and reverse them. There are two possible situations that can occur on the second operation: Choosing 2 tails (which occurs with probability 1/3): it results in 3 heads. Choosing 1 head and 1 tail (which occurs with probability 2/3): it results in 1 head. So the expected number of heads is 1/3*3+2/3*1=5/3.
```
10
```
```
{10,10,10}
```
```
Returns: 0.0
```
You reverse every coin three times, so after the operations there will be 10 tails and no heads.

{2,7,1,8,2,8}

Returns: 4.792639999999999

{916,153,357,729,183,848,61,672,295,936}

Returns: 498.1980774932278

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.