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

0)

 {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)

 {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)

 {2, 5, 6, 4, 9, 10, 6, 2} {2, 5, 6, 4, 9, 10, 6, 2}
Returns: 0.4999999999999999
3)

 {2, 5, 6, 4, 9, 10, 6, 2} {6, 7, 4, 5, 3, 2, 9, 1}
Returns: 0.5429014970733334
4)

 {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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10562

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14187&pm=10562

rng_58

Testers:

liympanda , konqueror , ivan_metelsky , keshav_57

Problem categories:

Dynamic Programming