Match Prediction
Time limit1sMemory limit256 MB
Given win/draw/loss probabilities for all six matches among four teams, compute each team's probability of finishing in the top two.
- Level
Medium4 of 10
- Topics
- Probability, Brute force, Implementation, Combinatorics
- Solved
- No attempts yet
Problem
Bored, Muji and Kon were watching TV when they came across a match in which the South Korean team was competing live.
The match they are watching is in the group stage, and the group containing South Korea has four countries competing.
The rules of the group stage are as follows.
- Four teams play in the group stage.
- Each team plays every other team once, for a total of 3 matches.
- The winner of a match earns 3 points, and if the match is a draw both teams earn 1 point each. The loser earns no points.
- After all group stage matches are played, teams are ranked by points. If teams are tied on points, their ranking is decided by a draw, and the draw is conducted fairly. After ranking, the top two teams advance to the next round.
Experts predicted, for all 6 matches of the group stage, the probability that a given team wins, draws, or loses. Assuming all matches are played independently (the result of any match does not affect the result of any other match), and that they go according to the experts' predictions, Muji and Kon became curious about the probability that each team advances through the group stage to the next round. But Muji and Kon could not compute the probabilities themselves, so they asked you for help. Help Muji and Kon solve this problem!
Input
The first line gives the names of the four countries that will play in the group stage, separated by spaces. Every country name is a string of length between 1 and 10 consisting only of uppercase English letters.
From the second line to the seventh line, lines are given in the order A B W D L, meaning that according to the experts' predictions, when A and B play a match, the probability that A wins is W, the probability that A draws is D, and the probability that A loses is L.
A and B are each one of the country names on the first line, and A and B are never the same. Also, W, D, and L are given with at most three decimal places, and W + D + L = 1 is guaranteed.
Output
On the i-th line, output the probability that the i-th country given in the input advances to the next round.
A result is accepted as correct only if the relative error or absolute error compared with the true answer is at most 10-6.