← 返回题目列表

Codeforces · 2023/D

D. 许多游戏

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

最近,您收到了一张稀有的门票,可以前往世界上唯一可以真正赚钱的赌场,并且您想充分利用这个机会。

该赌场的条件如下:

- 赌场里总共有 $$$n$$$ 游戏。
- 每个游戏最多可以玩一次。
- 每个游戏都有两个参数:$$$p_i$$$ ($$$1 \le p_i \le 100$$$) 和 $$$w_i$$$ - 赢得游戏的概率百分比和获胜奖金。
- 如果您在决定玩的任何游戏中失败,您将不会获得任何东西(即使是您赢得的游戏)。

您需要提前选择一组游戏,以便最大化您的预期奖金价值。

在这种情况下,如果您选择玩索引为 $$$i_1 < i_2 < \ldots < i_k$$$ 的游戏,那么您将以 $$$\prod\limits_{j=1}^k \frac{p_{i_j}}{100}$$$ 的概率赢得所有游戏,在这种情况下,您的奖金将等于$$$\sum\limits_{j=1}^k w_{i_j}$$$。

也就是说,您的奖金预期值为 $$$\left(\prod\limits_{j=1}^k \frac{p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)$$$。

为了避免破产,赌场老板限制了每场比赛的预期奖金价值。因此,对于所有 $$$i$$$ ($$$1 \le i \le n$$$),它认为 $$$w_i \cdot p_i \le 2 \cdot 10^5$$$。

您的任务是找到通过在赌场中选择一组游戏可以获得的最大期望奖金值。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 提供玩的游戏数量。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$p_i$$$ 和 $$$w_i$$$ ($$$1 \leq p_i \leq 100$$$, $$$1 \leq w_i, p_i \cdot w_i \leq 2 \cdot 10^5$$$) —第 $$$i$$$ 场比赛的获胜概率和奖金金额。

输出

输出一个数字——通过选择某些游戏子集可以获得的赌场奖金的最大预期值。

如果相对或绝对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,如果 $$$a$$$ 是您的答案,而 $$$b$$$ 是陪审团的答案,则如果 $$$\frac{|a-b|}{\max(b, 1)} \le 10^{-6}$$$ 则将被接受。

示例

输入 #1

3
80 80
70 100
50 200

输出 #1

112.00000000

输入 #2

2
100 1
100 1

输出 #2

2.00000000

输入 #3

4
1 100
2 1000
2 100
3 1

输出 #3

20.00000000

输入#4

5
34 804
78 209
99 191
61 439
90 79

输出#4

395.20423800

注意

在第一个示例中,您可以选择第一场和第三场比赛。在这种情况下,预期奖金值为 $$$\left(\frac{p_1}{100}\cdot \frac{p_3}{100}\right) \cdot (w_1 + w_3) = \left(\frac{80}{100}\cdot \frac{50}{100}\right) \cdot (80 + 200) = 112$$$。

在第二个示例中,您可以选择第一个和第二个游戏。在这种情况下,预期奖金值为 $$$\left(\frac{p_1}{100}\cdot \frac{p_2}{100}\right) \cdot (w_1 + w_2) = \left(\frac{100}{100}\cdot \frac{100}{100}\right) \cdot (1 + 1) = 2$$$。

在第三个示例中,您只能选择第二个游戏。在这种情况下,奖金的预期值为 $$$\frac{p_2}{100} \cdot w_2 = \frac{2}{100} \cdot 1000 = 20$$$。