1-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"C" Магический артефакт
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Максим играет в компьютерную игру. Она состоит из n уровней, которые пронумерованы от 1 до n. Их можно проходить в любом порядке, на i-й уровень Максим тратит ai секунд.

Кроме того, Максим может найти магический артефакт, который усилит его персонажа. Артефакт в игре ровно один, и его местонахождение точно неизвестно — на i-м уровне он находится с вероятностью pi. После получения артефакта играть становится существенно проще — с ним Максим проходит i-й уровень за bi секунд (bi ≤ ai). Обратите внимание, что артефакт не действует на том уровне, на котором Максим его нашёл.

Максим хочет проходить уровни в таком порядке, чтобы минимизировать математическое ожидание времени игры. Помогите ему вычислить, какого минимального математического ожидания он сможет добиться, выбрав некоторый порядок прохождения уровней. Максим выбирает порядок уровней заранее, этот порядок не должен зависить от того, на каком уровне окажется артефакт.

Математическим ожиданием случайной величины называется сумма по всем возможным исходам произведения вероятности этого исхода на значение величины. В данном случае исходы соответствуют тому, на каком уровне окажется артефакт, а значение величины — время прохождения, если артефакт оказался на этом уровне, а Максим проходит уровни в выбранном порядке.

Формат входных данных

Входные данные содержат несколько тестовых примеров. В первой строке задано одно число t — количество тестов (1 ≤ t ≤ 1000).

Каждый из тестов описывается следующим образом: в первой строке задано число n — количество уровней (1 ≤ n ≤ 105).

В следующих n строках описаны уровни. Каждый из них задаётся тремя целыми числами: ai, bi, xi — время прохождения уровня до и после нахождения артефакта и значение, которое помогает вычислить вероятность найти артефакт на этом уровне. Вероятность вычисляется по формуле pi = xi / 107 (1 ≤ bi ≤ ai ≤ 105; 0 ≤ xi ≤ 107; сумма всех xi равна 107).

Сумма n по всем тестам не превосходит 5·105.

Формат выходных данных

Для каждого теста выведите одно число — математическое ожидание времени игры при оптимальном выборе порядка прохождения уровней. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает 10 - 6.

Примеры
Входные данные
2
3
10 5 10000000
5 3 0
7 3 0
4
3 1 2500000
4 1 2500000
10 1 2500000
2 1 2500000
Выходные данные
16
10.25
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.