#P18095. Lottery
Lottery
Lottery
题目描述
奖池中有 件物品,第 件的价值为 。你必须至少抽奖一次。
每轮先支付当前费用 ,再等概率抽到 件物品中的一件。看到结果后,可以保留该物品并结束,也可以放弃该物品并进入下一轮;放弃后,下一轮费用变为 。各轮抽取相互独立,奖池不减少。
最终收益等于最后保留的物品价值减去所有轮次支付的费用。选择使期望收益最大的策略,求最大期望收益。
输入格式
第一行三个整数 。第二行 个整数 。
输出格式
输出一个实数。与正确答案的绝对误差或相对误差不超过 即可。
数据范围
,。
样例 1
输入
3 2 0
4 1 6
输出
2.000000000
样例 2
输入
9 8 2
53 71 5 6 80 37 50 33 90
输出
51.557786840