PseudoRandomKingdom
SRM 394 · 2008-03-22 · by Xixas
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
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.
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.
{"1","0 2 3","1","1"}
2
0
Returns: 0.037037037037037035
{"1","0 2 3","1","1"}
2
1
Returns: 0.14814814814814814
{"1","0 2 3","1","1"}
2
2
Returns: 0.4074074074074074
{"1","0 2 3","1","1"}
2
3
Returns: 0.7407407407407407
{"1","0 2 3","1","1"}
2
4
Returns: 1.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 2 3 4 5 6",
"0",
"0",
"0",
"0",
"0",
"0"}
10
19
Returns: 0.903158288086044
Almost all graphs satisfy us.
{"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.
{"1 6", "0 7", "5", "8 4", "9 3", "2 9", "0", "8 1", "7 3", "5 4"}
3
5
Returns: 0.007293701171875
next 5 are single paths
{"31", "11", "5", "11", "11", "2 20 15 28 10 26 42 34 25 44 41 31 43", "11", "11", "11", "11", "5", "48 1 6 35 30 33 4 21 15 14 8 24 7 17 40 36 9 3 13", "15", "11", "11", "37 49 11 12 32 45 16 5", "15", "11", "31", "31", "5", "11", "31", "31", "11", "5", "5", "31", "5", "31", "11", "5 47 23 22 29 27 18 39 0 19 46 38", "15", "11", "5", "11", "11", "15", "31", "31", "11", "5", "5", "5", "5", "15", "31", "31", "11", "15"}
10
40
Returns: 0.8615890488707026
next 2 are starry
Submissions are judged against all 81 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PseudoRandomKingdom with a public method double probabilityOfHappiness(vector<string> g, int cost, int savings) · 81 test cases · 2 s / 256 MB per case