RandomApple | Topcoder Archive

Problem Statement

Taro likes apples very much. He has N boxes numbered from 0 to N-1. There are K different types of apples numbered from 0 to K-1. You are given three String[]s, hundred, ten and one. Concatenate j-th characters in hundred[i], ten[i] and one[i] in this order to get a string that represents the number of j-th type apples in Box i (it may have leading zero(s)). This number will be between 0 and 199, inclusive.

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 a double[] that contains exactly K elements and whose i-th element is the probability that Taro chooses an i-th type apple.

Definition

Class:: RandomApple
Method:: theProbability
Parameters:: String[], String[], String[]
Returns:: double[]
Method signature:: double[] theProbability(String[] hundred, String[] ten, String[] one)
(be sure your method is public)

Notes

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

Constraints

N will be between 1 and 50, where N is the number of elements in hundred.
K will be between 1 and 50, where K is the number of characters in hundred[0].
ten and one will contain exactly N elements.
Each element in hundred, ten and one will contain exactly K characters.
Each character in hundred will be '0' or '1'.
Each character in ten and one will be a digit ('0'-'9').
Each box will contain at least one apple.

Examples

```
{"00"}
```
```
{"00"}
```
```
{"58"}
```
```
Returns: {0.38461538461538464, 0.6153846153846154 }
```
There is only one box which contains 5 type-0 apples and 8 type-1 apples. The probability of choosing a type-0 apple is 5 / 13.
```
{"00", "00"}
```
```
{"00", "00"}
```
```
{"21", "11"}
```
```
Returns: {0.5888888888888889, 0.4111111111111111 }
```
If he chooses only box 0 in the first step, the probability of choosing a type-0 apple is 2 / 3. If he chooses only box 1 in the first step, the probability of choosing a type-0 apple is 1 / 2. If he chooses both boxes in the first step, the probability of choosing a type-0 apple is 3 / 5. So the probability of choosing a type-0 apple is (2 / 3 + 1 / 2 + 3 / 5) / 3 = 53 / 90.

{"0000", "0000", "0000"}

{"2284", "0966", "9334"}

{"1090", "3942", "4336"}

Returns: {0.19685958571981937, 0.24397246802233483, 0.31496640865458775, 0.24420153760325805 }

{"01010110", "00011000", "00001000", "10001010", "10111110"}

{"22218214", "32244284", "68402430", "18140323", "29043145"}

{"87688689", "36101317", "69474068", "29337374", "87255881"}

Returns: {0.11930766223754977, 0.14033271060661345, 0.0652282589028571, 0.14448118133046356, 0.1981894622733832, 0.10743462836879789, 0.16411823601857622, 0.06090786026175882 }

```
{"10"}
```
```
{"00"}
```
```
{"00"}
```
```
Returns: {1.0, 0.0 }
```
One box with 100 type-0 apples and no type-1 apples.

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.