#7 「 小迟的比赛 」

统计

小迟最近去参加了一个锦标赛,这个锦标赛总共有$n$轮比赛,最终成绩由这$n$轮比赛中赢的轮数决定。至于小迟每一轮比赛的胜利概率,则取决于他在该轮比赛之前的战绩。也就是说,如果小迟在第$i$轮比赛选择积极应战,并且前$i-1$轮比赛中取得了$j$胜的话,那么第$i$轮比赛的胜率概率为$p[i][j]$,这里我们保证了一点就是对于同一个$i$,$p[i][j]$关于j的上升保持单调不上升(也就是说$p[i][j]\ge p[i][j+1]$)。

小迟观察到这个规则之后,想到了一个可能可以使他最终成绩更优的方法,就是在某些轮比赛采取第二种策略,故意求败,也就是以$100%$的概率输掉该轮比赛,从而使自己在后面能够遇到更容易对付的对手。

小迟现在已经看到了整个$p$数组,小迟希望你能告诉他一个最优的策略,使得他能最大化他的期望赢的轮数。

这里,定义一下期望。假如我们要求一个事件A的期望,那么假如事件A以$Pi$的概率结果为$i$,那么事件A的期望则是$i*Pi$的和,大概的含义就是结果值关于概率的一个加权平均数。

输入格式

输入数据第一行为轮数$n$,$n$为正整数。

接下来的$n$行,第$i$行有$i$个实数,表示对应的$p[i][0],….p[i][i-1]$。

输出格式

一行一个实数,表示最优策略下期望赢的轮数,保留两位小数。

样例数据

input

2
0.5
0.5 0.5

output

1.00

样例解释

由于我们看到对于第i轮,无论之前战绩如何,胜率都是相同的,因此,我们的最优策略应当是每一轮努力求胜。

然后,第一轮,如果我们赢了,概率为$0.5$,输了的概率也为$0.5$。

如果第一轮赢了,第二轮又赢了,概率为$0.5*0.5=0.25$,赢两盘;

如果第一轮赢了,第二轮输了,概率为$0.5*(1-0.5)=0.25$,赢一盘;

如果第一轮输了,第二轮赢了,概率为$(1-0.5)*0.5=0.25$,赢一盘;

如果两轮都输了,概率为$(1-0.5)*(1-0.5)=0.25$,赢零盘。

故期望赢的轮数为$0.25*2+(0.25+0.25)*1+0.25*0=1$。

数据规模与约定

$1 \le n \le 1000,0 \le p[i][j] \le 1 $。

时间限制:3s

空间限制:512MB

Author: Nineteen