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 |
|
|