ICPC North America Qualifier 2016, Problem B
Have you recently visited an arcade? Arcade games seem to have become more boring over the years, requiring less and less skill. In fact, most arcade games these days seem to depend entirely on luck. Consider the arcade game shown in the picture, which consists of different holes arranged in a triangular shape. A ball is dropped near the hole at the top. The ball either falls into the hole, in which case the game ends, or it bounces to one of its (up to)
Write a program that computes the expected payout when dropping a ball into the machine!
Input Specification
The input consists of a single test case. The first line contains an integer
These two lines are followed by
You can assume that after the ball has bounced
Output Specification
Output a single number, the expected value from playing one game. Your answer is considered correct if its absolute or relative error is less than
Hint: Using Monte Carlo-style simulation (throwing many balls in the machine and simulating which hole they fall into using randomly generated choices) does not yield the required accuracy!
Sample Input 1
4
40 30 30 40 20 40 50 30 30 50
0.0 0.0 0.45 0.45 0.1
0.0 0.3 0.3 0.3 0.1
0.3 0.0 0.3 0.3 0.1
0.0 0.3 0.3 0.3 0.1
0.2 0.2 0.2 0.2 0.2
0.3 0.0 0.3 0.3 0.1
0.0 0.8 0.0 0.0 0.2
0.4 0.4 0.0 0.0 0.2
0.4 0.4 0.0 0.0 0.2
0.8 0.0 0.0 0.0 0.2
Sample Output 1
32.6405451448
Sample Input 2
2
100 50 50
0.0 0.0 0.45 0.45 0.1
0.0 0.90 0.0 0.0 0.10
0.90 0.0 0.0 0.0 0.10
Sample Output 2
76.31578947368
Comments