P3610.第3题-铁制品工艺练习赛
题目内容
铁制品工艺练习赛(Iron Craft Practising Contest，ICPC)赛季即将开始。在接下来的连续 n 周内，每周将在某个城市举行一次比赛。
根据经验，小C在第 i 场比赛中成功打铁的概率为 pi 。
如果小C参加比赛，则在赛后有 qi 的概率被教练禁止参加下一周（即第 i+1 周）的比赛。无论他是否参加第 i+1 周的比赛，此禁令都会在第 i+1 周结束后自动解除。
小C可以选择任意场比赛参加。小C希望最大化本赛季打铁次数的期望值。
【名词解释】
期望值：期望值是概率论中的一个概念，指随机变量在多次试验中的平均结果。例如，投掷一枚均匀硬币，正面向上得分 1 ，反面向上得分 0 ，其期望值为 0.5 。
输入描述
第一行输入一个整数 n(1≤n≤106)，表示比赛场次数。
接下来 n 行，每行输入两个实数 pi,qi(0≤pi,qi≤1)，其中：
- pi 表示第 i 场比赛成功打铁的概率；
- qi 表示第 i 场比赛后被禁止参加下一场比赛的概率。
输出描述
输出一个实数，表示小C本赛季打铁次数的最大期望值。
由于浮点数计算可能产生误差，当误差的量级不超过 10−6 时，答案将被接受。
具体来说，设你的答案为 a，标准答案为 b ，当且仅当
max(1,∣b∣)∣a−b∣≤10−6 时，答案被接受。
样例1
输入
2
0.5 0.5
0.5 0.0
输出
0.75
说明
-
第 1 场比赛：成功概率 0.5 ，禁赛概率 0.5。
-
在第 1 场之后，有 0.5 的概率被禁赛，此时无法参加第 2 场；有 0.5 的概率可继续参加。
-
如果继续参加，则在第 2 场比赛中成功概率为 0.5 。
-
因此期望值为 0.5+0.5×0.5=0.75 。
样例2
输入
5
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0
输出
5.0
说明
在该样例中，每场比赛都必定成功且不会被禁赛，因此总期望打铁次数为 5 。
