← 返回题目列表

AtCoder · icpc2014autumn_c

C. 极速奔跑

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

问题陈述

无限编年史-公主城堡- 是一款简单的角色扮演游戏。 有 $n + 1$ 个检查点,编号为 $0$ 到 $n$, 对于每个 $i = 1, 2, \ldots, n$,都有一条从检查点 $i - 1$ 到 $i$ 的唯一单向道路。 游戏从检查点 $0$ 开始,到检查点 $n$ 结束。 邪恶的怪物会出现在道路上,英雄将与它们进行战斗。 您可以在任何关卡保存游戏进度;如果你输了一场战斗,你可以从你上次保存的检查点重新开始游戏。 游戏开始时,进度会自动保存在检查点$0$处,没有时间。

兔子花子很喜欢这个游戏,现在对速通感兴趣。 虽然花子是游戏高手,但由于随机因素,她并不总是能赢得战斗。 对于每个 $i$,她估计了从检查点 $i - 1$ 到 $i$ 沿途赢得所有战斗的概率 $p_i$。 每次她从检查点 $i - 1$ 开始,正好一分钟后, 她将以 $p_i$ 的概率到达检查点 $i$,并且以 $1 - p_i$ 的概率她最后一次保存的位置。

让花子困惑的是,在检查站保存进度也需要一分钟(!), 因此,为了快速前进,通过一些检查站而不保存可能是个好主意。 任务是计算完成游戏所需的最短预期时间。


输入

输入由多个数据集组成。数据集数量不超过 50 美元。 每个数据集有两行:第一行包含一个整数$n$($1 \le n \le 10^5$),代表道路数量, 第二行包含$n$个数字$p_1, p_2, \ldots, p_n$ ($0 \lt p_i \le 1$),代表获胜概率。 每个 $p_i$ 正好有小数点后两位数字。 输入的末尾表示为仅包含一个零的行。

输出

对于每个数据集,在一行中显示最短预期时间(以分钟为单位),相对误差最多为 $10^{-8}$。


示例输入

2
0.50 0.40
2
0.70 0.60
4
0.99 1.00 1.00 0.01
0

样本输入的输出

5.5000000000
4.0476190476
104.0101010101