← 返回题目列表

Codeforces · 268/E

E. 播放列表

中文机器翻译题面 查看原题

Manao的朋友经常给他发新歌。他从来不会立即听他们的。相反,他将它们编译成一个播放列表。当他觉得自己的思想对新音乐持开放态度时,他会打开播放列表并开始听歌曲。

当然,有些歌曲Manao并不是特别喜欢。为了从接收到的歌曲中获得更多乐趣,他发明了以下收听播放列表的程序:

- 如果听完某首歌后 Manao 意识到他喜欢它,那么他就会记住它并开始听下一首未听过的歌曲。
- 如果听完某首歌后 Manao 意识到他不喜欢这首歌,他会听完迄今为止他喜欢的所有歌曲,然后开始听下一首未听过的歌曲。

例如,如果Manao的播放列表中有四首歌曲,A、B、C、D(按相应的顺序),并且他最终会喜欢歌曲A和C,那么收听的顺序如下:

1.马瑙听A,他喜欢,他记得。
2. Manao听B,他不喜欢,所以他又听A。
3. Manao听C,他喜欢这首歌,他也记得这首歌。
4. Manao 听了 D,但不喜欢它,并重新听了歌曲 A 和 C。

也就是说,最终Manao听了歌曲A 3次,歌曲C 2次,歌曲B和D各1次。请注意,如果马瑙曾经喜欢过一首歌,那么他在以后的聆听中永远不会不喜欢它。

Manao 已收到 n 首歌曲:其中第 i 首歌曲长度为 li 秒,Manao 可能会以 pi 百分比的概率喜欢它。这些歌曲可以按任​​何顺序进入 Manao 的播放列表,因此 Manao 想知道对于播放列表中歌曲的所有可能排列,收听过程结束后的最大预期秒数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50000)。以下 n 行中的第 i 行包含两个整数,由一个空格分隔 — li 和 pi (15 ≤ li ≤ 1000, 0 ≤ pi ≤ 100) — 第 i 首歌曲的长度(以秒为单位)以及 Manao 喜欢这首歌的概率(以百分比为单位)。

输出

在一行中打印一个实数——所有歌曲排列的最大预期收听时间。如果绝对误差或相对误差不超过 10 - 9,则答案将被视为有效。

示例

输入 #1

3
150 20
150 50
100 50

输出 #1

537.500000000

输入 #2

4
300 0
300 50
240 50
360 80

输出 #2

2121.000000000

注意

考虑第一个测试用例。如果Manao按照最初编排的顺序听歌曲,数学期望将等于467.5秒。通过将第一首歌曲放在播放列表的末尾来获得最大期望值。

考虑第二个测试用例。应该先听这首360秒长的歌曲。真尾肯定会不喜欢的300秒长的歌曲应该放在最后。