← 返回题目列表

Codeforces · 2208/C

C. 耐力和任务

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

有 $$$n$$$ 任务等着你。任务 $$$i$$$ 的整数值为 $$$c_i$$$,难度为 $$$p_i$$$。另外,你的初始耐力为$$$1$$$,表示为$$$S$$$。您应该处理从任务 $$$1$$$ 到任务 $$$n$$$ 的任务。对于每项任务,您有两种选择。

  • 放弃任务。这样,就不会发生什么事情了。
  • 完成任务。这样,您将获得 $$$S\cdot c_i$$$ 积分。然而,$$$S$$$ 将下降到 $$$S\cdot (1-\frac{p_i}{100})$$$ 之后 任务已完成。

完成该过程后,您需要最大化您的积分。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le10^5$$$) 表示任务数。

以下 $$$n$$$ 行每行包含两个整数,表示 $$$c_i$$$ ($$$1\le c_i\le 100$$$) 和 $$$p_i$$$ ($$$0\le p_i\le 100$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个实数 - 您可以获得的最大可能分数。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a−b|}{\max(1,|b|)}\le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入
复制

2
2
10 0
20 5
3
10 5
10 80
20 5

输出
复制

30.0000000000
29.0000000000

注意

在第一个测试用例中,最好按顺序完成任务$$$1$$$ 和$$$2$$$,获得$$$10+20=30$$$ 积分。

在第二个测试用例中,最佳完成任务$$$1$$$,放弃任务$$$2$$$,并完成任务$$$3$$$。在完成任务 $$$3$$$ 之前,你的耐力已降至 $$$1-\frac{5}{100}=0.95$$$。所以你总共获得$$$10+20\cdot 0.95=29$$$点。