ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Improbability Theory

Time limit: 2.0 second
Memory limit: 64 MB
Prof. W. Booster, a famous Galactic Institute professor, continues his work on the Ultimate Improbability Theory. Currently, it consists of n hypotheses. Some of them are based on other hypotheses of the Theory. Like any other theory which deals with Improbability effects, Booster's one is extremely complicated so there's nothing surprising about the fact that cause-and-effect relations between the hypotheses can form cycles.
After several desperate, but still rather unsuccessful attempts to explain results of the very last experiment by means of the Theory, the professor began to suspect that something must be definitely wrong with some of the hypotheses.
To search for mistakes in the Improbability Theory Prof. Booster constructed a special computer which allows to determine in ti seconds whether i-th hypothesis is admissible. The computer can check hypotheses in any order but no more than one at a time. The professor also managed to compute the probabilities pi of the i-th hypothesis being admissible. It is known that the admissibility of any hypothesis doesn't depend in any way on the admissibility of any other hypothesis.
The professor considers a hyphothesis correct if it's admissible and all of the hypotheses it is (directly or indirectly) based upon are admissible too. Now Prof. Booster is going to positively identify which of hypotheses are correct and which are not. Help him to calculate the expected time it will take if the checking process would be organized in an optimal way.


The first line contains the number of hypotheses in the Improbability Theory n (1 ≤ n ≤ 500). Next n lines describe hypotheses. The i-th of these lines starts with three numbers ti (1 ≤ ti ≤ 1000), pi (0.0001 ≤ pi ≤ 0.9999), and ki (0 ≤ ki < n), followed by ki different numbers of hypotheses the i-th hypothesis is directly based upon. No hypothesis is directly based upon itself. Hypotheses are numbered with integers from 1 to n. All ti are integers.


Output the expected time required to determine the correctness of every hypothesis. The answer must be accurate up to 10−3.


5 0.3 1 2
6 0.99 0
2 0.2 1 4
2 0.2 0
1 0.5 1 2
2 0.5 1 3
3 0.5 1 1
Problem Author: Damir Akhmetzyanov
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1751. Improbability Theory