Editorial for DMOPC '14 Contest 2 P5 - Sawmill Scheme
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
This is a graph theory problem. The graph is a DAG (Directed Acyclic Graph) and we can use dynamic programming to find probabilities.
is the probability of a log floating to lake
. In the edge from
to
, we will call
the child of
. For each child of
, add
to its probability (
), as we have an equal probability of selecting a river to flow to.
At the end, output the value for all lakes which have no children. Be careful to output at least 9 digits. Fast input and output methods should be used if possible.
Comments