Facebook Hacker Cup 2015 Round 3
Mr. Fox sure loves his rocks! In fact, when he's not in a hurry, he often looks at the rocks lying around near him to decide where to wander in his forest.
Mr. Fox lives in a forest with clearings, numbered from
to
, with
one-way trails initially running amongst them. The
th trail runs from clearing
to a different clearing
, and is littered with
rocks. No two clearings are connected by multiple trails running in the same direction, though they could be connected by 2 trails running in opposite directions. Additionally, an interesting property of this forest is that a trail from clearing
to clearing
may only exist if
.
To entertain himself over a period of days, Mr. Fox will cause one event to occur on each day. The
th event may be one of 3 types, determined by the value of
:
Given 3 integers
,
, and
, Mr. Fox will create a new trail from clearing
to a different clearing
, and drop
rocks onto it. It's guaranteed that no trail from
to
will exist at the start of the
th day, and that
will hold.
Given 2 distinct integers
and
, Mr. Fox will completely destroy the trail from clearing
to clearing
(which is guaranteed to exist at the start of the
th day). Note that, once such a trail is destroyed, a new trail from
to
may be created in the future.
Given 2 distinct integers
and
, Mr. Fox will take a "random stroll" starting at clearing
, and would like to determine the probability that he'll visit clearing
at least once during it.
A "random stroll" consists of repeating the following process potentially infinitely: If Mr. Fox is currently in some clearing
, and there are no outgoing trails from
, then the stroll ends immediately. Otherwise, he'll consider all of the rocks on all of the outgoing trails from
, choose one of these rocks uniformly at random, follow the trail on which that rock lies to its destination clearing (without removing any rocks), and repeat the process from his new clearing.
For each event of type 3, output the requested probability.
Input
Input begins with an integer , the number of test cases. For each test case, there is first a line containing the space-separated integers
,
, and
.
Then, lines follow, the
th of which contains the space-separated integers
,
, and
.
Then, lines follow, the
th of which contains the space-separated integers
,
, and
. If
, this line additionally contains the integer
.
Output
For the th test case, print a line containing
Case #i:
followed by the computed probabilities for each stroll that Mr. Fox takes. These probabilities should be space-separated, and rounded to 6 decimal places.
Absolute errors of up to will be ignored.
Constraints
Explanation of Sample
In the first test case, Mr. Fox does multiple strolls from clearing 0 while looking out for clearing 3.
His first stroll has probability 1 as he must always end up at clearing 3.
His second stroll has probability 1/2 as there's a 50% chance he gets stuck in clearing 4.
His third stroll has probability 2/3 as he now only goes to clearing 4 1/3 of the time.
His fourth stroll has probability 1/3 as he gets stuck in clearing 4 1/3 of the time, and in clearing 1 1/3 of the time.
Sample Input
5
8 0 10
1 0 1 1
1 1 2 1
1 2 3 1
3 0 3
1 0 4 1
3 0 3
1 0 3 1
3 0 3
2 1 2
3 0 3
4 4 10
0 1 1
1 0 1
1 2 1
0 3 1
3 0 2
2 0 1
1 0 1 2
3 0 2
2 0 1
1 0 1 3
3 0 2
2 0 1
1 0 1 4
3 0 2
8 7 5
0 1 1
1 2 1
2 3 1
0 4 1
1 5 1
2 6 1
3 7 1
3 0 5
3 0 7
1 3 0 1
3 0 5
3 0 7
8 4 10
4 5 1
5 6 1
6 7 1
7 4 1
1 0 4 1
1 0 1 4
3 0 7
1 1 6 1
3 0 7
1 1 2 1
1 2 3 1
3 0 7
1 2 0 1
3 0 7
12 5 7
0 4 1
4 8 1
0 1 1
1 2 1
2 3 1
3 0 8
1 1 4 1
3 0 8
1 2 4 1
3 0 8
1 3 4 1
3 0 8
Sample Output
Case #1: 1.000000 0.500000 0.666667 0.333333
Case #2: 0.333333 0.500000 0.600000 0.666667
Case #3: 0.250000 0.125000 0.266667 0.066667
Case #4: 0.200000 1.000000 0.600000 0.750000
Case #5: 0.500000 0.750000 0.875000 1.000000
Comments