RandomAppleEasy
Member SRM 478 · 2009-12-03 · by rng_58
Problem Statement
-
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.
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.
{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
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomAppleEasy with a public method double theRed(vector<int> red, vector<int> green) · 80 test cases · 2 s / 256 MB per case