题号:NC238613
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
有

种等级的物品,等级编号为

至

。对于任意
)
你可以消耗

个等级为

的物品,合成一个等级为

的物品。等级

的物品无法被合成,等级

的物品无法被消耗。
每一次合成有两种合成方式,第一种合成方式会以

的概率返还一个等级

的物品,第二种合成方式会以

的概率额外生成一个等级为

的物品。
现在给定你目前拥有的各个等级的物品数目,你希望通过若干次合成后,获得至少

个等级为

的物品。问,在最优策略下,有多大的概率可以达成目标呢?
注:你的最优策略是依赖于每一步的掉落结果的。例如最优策略是先进行一次等级

的第一种合成,若它没有掉落,则执行某个下一步策略

;若掉落了,执行某个下一步策略

,策略

和策略

均是你的最优策略的一部分。
你的答案与标准答案的差别不应超过

。
输入描述:
第一行正整数
。
再接下来一行两个正实数
。
接下来一行
个数字
至
,分别表示你初始拥有的第
种物品至第
种物品的数量。
,
,
输出描述:
一行一个浮点数,表示最优策略下的达成条件的概率。