Magic Artifact
Time limit2sMemory limit512 MB
Choose a fixed level order minimizing expected time when one unknown level hides an artifact; each level runs at ai before finds contract a_i-b_i from all later levels.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Math, Implementation
- Solved
- No attempts yet
Problem
Maxim is playing a video game. It has n levels, numbered from 1 to n. Levels can be completed in any order, and it takes Maxim ai seconds to complete the i-th level.
Maxim can find a magic artifact at one of the levels. There is exactly one magic artifact in the game, and once found it increases the speed of Maxim's hero and reduces the time needed to complete a level. However, it is not known where the artifact is; the probability that it is at the i-th level is pi. The time needed to complete the i-th level after the artifact is found is bi seconds (bi ≤ ai). The artifact does not reduce the time needed to complete the level where it is found.
Maxim wants to choose the order in which he completes the levels to minimize the expected time to complete the game. Help him find the minimal possible expected time. Maxim must choose the order to complete the levels before playing the game, and the order must not depend on whether the artifact was found at some level.
Recall that the expectation of a random variable is the sum over all possible outcomes of the product of the probability of such an outcome and the value of the variable. In this problem the outcome corresponds to the level where the artifact is, and the value is the total time needed if the artifact is at that level.
Input
Input data contains several test cases. The first line contains t, the number of test cases (1 ≤ t ≤ 1000).
Each test case is described as follows. The first line contains integer n, the number of levels (1 ≤ n ≤ 105).
The following n lines describe levels. Each level is specified with three integers ai, bi and xi: the time to complete the level before the artifact was found, the time to complete it after the artifact was found, and the value that helps to find the probability to find the artifact at that level. The probability is calculated using the formula pi = xi / 107 (1 ≤ bi ≤ ai ≤ 105; 0 ≤ xi ≤ 107; the sum of all xi is 107).
The sum of values of n in all test cases of one input data is at most 5·105.
Output
For each test case output one floating point value: the expected time to complete the game if the optimal order was chosen. The answer must have an absolute or relative error of at most 10-6.