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 |
| 0) | |
| | | 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.
|
|
|
| 1) | |
| | {"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.
|
|
|
| 2) | |
| | {"0000", "0000", "0000"} | {"2284", "0966", "9334"} | {"1090", "3942", "4336"} |
| Returns:
{0.19685958571981937, 0.24397246802233483, 0.31496640865458775, 0.24420153760325805 } | |
|
| 3) | |
| | {"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 } | |
|
| 4) | |
| | | Returns: {1.0, 0.0 } | | One box with 100 type-0 apples and no type-1 apples. |
|
|