莫娜与阿贝多
题号:NC238613
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

m种等级的物品,等级编号为1m。对于任意你可以消耗3个等级为k的物品,合成一个等级为的物品。等级1的物品无法被合成,等级m的物品无法被消耗。

每一次合成有两种合成方式,第一种合成方式会以p的概率返还一个等级k的物品,第二种合成方式会以q的概率额外生成一个等级为的物品。

现在给定你目前拥有的各个等级的物品数目,你希望通过若干次合成后,获得至少n个等级为m的物品。问,在最优策略下,有多大的概率可以达成目标呢?

注:你的最优策略是依赖于每一步的掉落结果的。例如最优策略是先进行一次等级k的第一种合成,若它没有掉落,则执行某个下一步策略A;若掉落了,执行某个下一步策略B,策略A和策略B均是你的最优策略的一部分。

你的答案与标准答案的差别不应超过

输入描述:

第一行正整数n,m
再接下来一行两个正实数p,q
接下来一行m个数字a_1a_m,分别表示你初始拥有的第1种物品至第m种物品的数量。

,,

输出描述:

一行一个浮点数,表示最优策略下的达成条件的概率。
示例1

输入

复制
2 3
0.5 0.5
9 0 0

输出

复制
0.5625
示例2

输入

复制
3 4
0.3 0.1
12 3 2 0

输出

复制
0.016759