Codeforces Round 164 (Div. 2) |
---|
Закончено |
Друзья Манао часто присылают ему новые песни. Обычно он слушает их не сразу, а собирает их в плейлист. Когда он чувствует, что его ум открыт для новой музыки, он включает этот плейлист и начинает прослушивать песни.
Конечно, Манао нравится далеко не каждая песня. Чтобы получить побольше удовольствия от присланных песен, он придумал следующую процедуру прослушивания плейлиста:
Например, если у Манао в плейлисте четыре песни A, B, C, D (в соответствующем порядке) и ему в итоге понравятся песни A и C, тогда порядок прослушивания получится следующий:
То есть в итоге Манао прослушает три раза песню A, два раза песню C и по одному разу песни B и D. Заметим, что если песня однажды понравилась Манао, она не может разонравиться ему при следующем прослушивании.
Манао прислали n песен: i-ая из них длится li секунд и может понравиться Манао с вероятностью pi процентов. Песни могли попасть в плейлист Манао в любом порядке, поэтому Манао хочет знать максимальное математическое ожидание количества секунд, после которого процесс прослушивания закончится, по всем возможным перестановкам песен в плейлисте.
В первой строке записано единственное целое число n (1 ≤ n ≤ 50000). В i-ой из следующих n строк записаны два целых числа, разделенные одним пробелом — li и pi (15 ≤ li ≤ 1000, 0 ≤ pi ≤ 100) — длина i-той песни в секундах и вероятность, того что эта песня понравится Манао, в процентах.
В единственной строке выведите одно вещественное число — максимальное по всем перестановкам песен математическое ожидание длительности процесса прослушивания. Ответ будет считаться верным, если абсолютная или относительная погрешность не будет превышать 10 - 9.
3
150 20
150 50
100 50
537.500000000
4
300 0
300 50
240 50
360 80
2121.000000000
Рассмотрим первый тестовый пример. Если слушать песни в том порядке, в котором они заданы изначально, математическое ожидание будет равно 467.5 секунд. Максимальное математическое ожидание получается, если переставить первую песню в конец плейлиста.
Рассмотрим второй тестовый пример. Песню длиной 360 секунд нужно слушать первой, а песню длиной 300 секунд, которая определенно не понравится Манао — последней.
Название |
---|