Author: | И. Блинов | Time limit: | 2 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
Risorius is playing his favorite game, Doka 2, where a new event, "Fallen Crown," has been added. The event is represented as a sequence of n consecutive transitions. When at checkpoint i, Risorius can only transition to checkpoint i+1. To move from checkpoint i to checkpoint i+1, three tokens ti1,ti2,ti3 must be collected. After transitioning from one checkpoint to the next, all accumulated tokens are lost.
The game includes h heroes, and for defeating the j-th hero, tokens tj1,tj2,tj3 are awarded. The probability of Risorius winning against the k-th hero is pk. Additionally, if the player loses against a particular hero 10 times consecutively while staying on the same checkpoint, they are awarded all three tokens regardless of the outcome.
The event starts at checkpoint 0 and ends upon reaching checkpoint n. Find the expected number of matches Risorius must play to complete the event, assuming optimal strategy.
The first line contains a single integer n. The next n lines each contain three integers ti1,ti2,ti3 (for each checkpoint). The following line contains a single integer h. The next h lines each contain four integers tj1,tj2,tj3, and pj (for each hero, where pj represents the win probability). It is guaranteed that a solution always exists.
Output a single floating-point number with two decimal places, representing the expected value of the number of matches required.
1≤n,h≤100000 1≤ti1,ti2,ti3,tj1,tj2,tj3≤109 0≤pj≤100
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|