Processing math: 100%

Problem E. Explorer kit

Author:И. Блинов   Time limit:2 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

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.

Input format

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 format

Output a single floating-point number with two decimal places, representing the expected value of the number of matches required.

Constraints

1n,h100000 1ti1,ti2,ti3,tj1,tj2,tj3109 0pj100

Sample tests

No. Standard input Standard output
1
3
1 2 3
1 1 1
3 4 5
5
1 2 2 50
1 3 4 25
5 1 1 25
5 5 5 100
6 7 8 100
16.32
2
1
1 1 1
1
1 2 2 50
5.99

0.060s 0.010s 13