RandomAppleEasy | Topcoder Archive

Problem Statement

Taro likes apples very much. He has N boxes numbered from 0 to N-1. Box i contains red[i] red apples and green[i] green apples. He decided to choose one apple from his boxes, and he does so in the following way:

First Step: He chooses a non-empty subset of his N boxes randomly and transfers all apples from those boxes to another box (this is a box other than the original N boxes and it is initially empty). Each non-empty subset of boxes has the same probability of being chosen.
Second Step: He chooses one apple from the new box randomly. Each apple in the box has the same probability of being chosen.

Return the probability that Taro chooses a red apple.

Definition

Class:: RandomAppleEasy
Method:: theRed
Parameters:: int[], int[]
Returns:: double
Method signature:: double theRed(int[] red, int[] green)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.

Constraints

red will contain between 1 and 50 elements, inclusive.
red and green will contain the same number of elements.
Each element of red and green will be between 1 and 10, inclusive.

Examples

```
{5}
```
```
{8}
```
```
Returns: 0.38461538461538464
```
There is only one box which contains 5 red apples and 8 green apples. The probability of choosing a red apple is 5 / 13.
```
{1, 2}
```
```
{1, 1}
```
```
Returns: 0.5888888888888888
```
If he chooses only box 0 in the first step, the probability of choosing a red apple is 1 / 2. If he chooses only box 1 in the first step, the probability of choosing a red apple is 2 / 3. If he chooses both boxes in the first step, the probability of choosing a red apple is 3 / 5. So the probability of choosing a red apple is (1 / 2 + 2 / 3 + 3 / 5) / 3 = 53 / 90.

{2, 5, 6, 4, 9, 10, 6, 2}

{2, 5, 6, 4, 9, 10, 6, 2}

Returns: 0.4999999999999999

{2, 5, 6, 4, 9, 10, 6, 2}

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

Returns: 0.5429014970733334

{5, 1, 2, 8, 4, 1, 1, 2, 3, 4, 5, 2, 10, 2, 6, 2, 8, 7, 9, 3}

{4, 7, 1, 1, 10, 3, 4, 1, 6, 2, 7, 6, 10, 5, 2, 9, 3, 8, 1, 8}

Returns: 0.46460213827476854

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.