#C2023J. 逛第二次超市
逛第二次超市
本题与逛超市的区别仅在于盲盒中剩下物品的要求,以及本题的数据范围为。
没想到吧,我居然在这里!
题目描述
野豌豆正在参加超市抽奖活动,抽奖活动共有个奖项,奖池中第个奖项总共有份,如果抽中第个奖项将会获得一份价值为的奖品。抽奖方式为从盲盒里抽签,初始时盲盒中总共有份签,其中表示第个奖项的签数总共有个。商店老板绝对公平,保证你抽到每个签的概率是相等的。
现在野豌豆仅获得了一次抽奖的机会,不过当野豌豆逛完超市来抽奖时已经来晚了,商店老板告诉你现在盲盒里剩下不超过份签了(即剩下奖品的总数不超过个),但好消息是每种奖项的奖品至少还剩下一份。野豌豆此时心中有种不祥的预感,于是他想问你在最坏情况下,自己抽到奖品的期望价值最小是多少。
关于期望的定义:假设抽到第个奖项的概率为,那么抽奖一次获得奖品的期望价值为
输入格式
第一行包含两个正整数和,表示总共有个奖项,且余下奖品总数不超过个。
第行包含两个正整数,表示第个奖项在初始时总共有份,抽中第个奖项时会获得价值为的奖品。
输出格式
输出一个小数,为野豌豆最坏情况下抽到奖品的期望价值,要求与答案的相对误差或绝对误差不超过。
也就是说,如果你给出的答案是,正确答案是,你的答案被认为是正确的当且仅当。
样例
5 10
3 1
4 5
3 6
1 7
1 10
4.4285714286
5 5
20 3000
10 1000
3 64800
100 2
100 1
13760.6000000000
数据范围
对于的数据,,,。
对于的数据,,, ,。
提示
对于第一组数据,可以证明当所剩奖品的价值分别是时,野豌豆可以抽到的期望价值最小,为$\frac 37\times 1 + \frac {1}{7}\times 5 + \frac 17 \times 6+\frac 17\times 7 + \frac 17\times 10 = \frac {31}{7} $
对于第二组数据,因为每种奖品都至少剩下一份,所以所剩商品的价值只能为,答案为。
相关
在下列比赛中: