Problem Statement |
| | There are n cities in a kingdom, numbered 0 through n-1. Some pairs of cities are connected by bidirectional roads in such a way that one can traverse all the cities in the kingdom by following these roads. There are exactly n-1 roads. The configuration of the roads is given as a String[] g, where the i-th element is a single-space separated list of the cities connected to city i by direct roads.
A spendthrift king devised the following scheme for taxing the roads: Each road is assigned a random integer between 0 and cost, inclusive, where each such integer is equally likely. This integer is the cost in dollars of traversing the road. John lives in one of the cities in the kingdom, and he is not happy to learn about these taxes. His fiancee Mary lives in another city, and he wants to go visit her. However, he only has savings dollars to spend on taxes. Return the probability that John will be able to reach Mary, regardless of where they each live. In other words, return the probability that the cost of travel between any two cities in the kingdom will not be greater than savings.
|
| |
Definition |
| | | Class: | PseudoRandomKingdom | | Method: | probabilityOfHappiness | | Parameters: | String[], int, int | | Returns: | double | | Method signature: | double probabilityOfHappiness(String[] g, int cost, int savings) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The returned value must be accurate to within a relative or absolute value of 1E-9. |
| |
Constraints |
| - | g will contain n elements, where n is between 2 and 50, inclusive. |
| - | Each element of g will contain between 0 and 50 characters, inclusive. |
| - | Each element of g will be a single-space seperated list of distinct integers with no leading zeroes, each of which will be between 0 and n - 1, inclusive. |
| - | i will not appear in the list g[i]. |
| - | i will appear in the list g[j] if and only if the number j will appear in the list g[i]. |
| - | g will represent a graph with the properties described in the problem statement. |
| - | cost will be between 1 and 10, inclusive. |
| - | savings will be between 0 and 500, inclusive. |
| |
Examples |
| 0) | |
| | {"1 2",
"0",
"0 3",
"2"} | 1 | 2 |
| Returns: 0.875 | | This is a path of length 3 so no more than two roads can have cost 1. We have 8 possible graphs in all and only the one where every road has a cost of 1 does not suit us. Thus the answer is 7/8. |
|
|
| 1) | |
| | {"1 2 3 4 5 6",
"0",
"0",
"0",
"0",
"0",
"0"} | 10 | 19 |
| Returns: 0.903158288086044 | | Almost all graphs satisfy us. |
|
|
| 2) | |
| | {"1 2 3 4 5 6",
"0",
"0",
"0",
"0",
"0",
"0"} | 10 | 0 |
| Returns: 5.644739300537775E-7 | | Now John does not have any savings at all. |
|
|
| 3) | |
| | | Returns: 1.0000000000000002 | |
|
| 4) | |
| | {"9 6",
"6 4",
"8",
"5",
"7 1",
"8 3",
"1 0 8",
"4",
"2 5 6",
"0"} | 9 | 26 |
| Returns: 0.350862063 | |
|