問題文
在这个游戏中,通过支付金钱和抽签,你可以赢得由一定概率分布决定的偶像。 1 人们可以获得它。
高桥君想要收集所有偶像。
彩票 M 有不同的类型,每个抽奖的每个偶像出现的概率都不同,1 中奖所需金额不同。
如果高桥采取最优策略收集所有偶像,求出期望需要的金钱数量。 在
入力
N M
C_1 cost_1
idol_{1,1} p_{1,1}
idol_{1,2} p_{1,2}
:
idol_{1,C_1} p_{1,C_1}
:
C_M cost_M
idol_{M,1} p_{M,1}
idol_{M,2} p_{M,2}
:
idol_{M,C_M} p_{M,C_M}
- 1 行中,一个整数表示空闲总数。 N(1≦N≦10),代表彩票类型的整数 M(1≦M≦4)由半角空格分隔。 来自行
- 2 行之后 i(1≦i≦M) 有关抽奖的信息以半角空格分隔。
- 整数 C_i (1≦C_i≦N) 是 代表第i 次抽签中包含的偶像数量。 代表抽取第
- 整数 cost_i (1≦cost_i≦3000) 是 代表第i 张彩票所需的价格。
- C_i 和 cost_i 从那时起,i 抽签中包含的偶像信息是 给予 j(1≦j≦C_i) 次。 包含在第
- 整数 idol_{i,j} (1≦idol_{i,j}≦N) 是 代表第i 期抽奖中 这是第 j 个偶像。 表示第
- 整数 p_{i,j} (1≦p_{i,j}≦100) 是 代表第i 期抽奖中 这是第 j 个偶像的出现概率,以百分比表示。 将第
- i 期抽签中所有偶像的出场率相加, 它变成100 。
部分点
-
针对此问题设置了部分分数。
如果所有满足
- N=1 和 M=1 的输入均得到正确回答, 如果所有满足10 点。
- N=1 的输入均被正确回答,则 10 点。
- C_i=1 的输入均被正确回答,则 10 点。
- N≦2 的输入均被正确回答,则 20 点。
- M=1 的输入均被正确回答,则 20 点。
- 如果所有测试用例都正确回答, 添加 30 点,总计 100 点。
出力
输出至少具有绝对误差和相对误差之一。 10^{-6} 或更少是可以接受的。
请在输出末尾添加换行符。
对于那些不知道如何解决的人
另外,问题D的难度水平也大致相同。我建议阅读这两个问题。
入力例 1
5 2 2 300 3 5 4 95 3 500 5 20 1 30 2 50
出力例 1
9343.17042606516
- 偶像是 5 类型,抽奖 2 类型。 在第
- 1 期抽奖中 2 你可以获得不同种类的偶像,1 每次会话费用 需要 300 。 第
- 1 期抽奖中 这是第 1 个偶像是闲人 3 ,出现的概率是 5% 。
- 1 期抽奖中 这是第 2 个偶像是闲人 4 ,出现的概率是 95% 。
- 2 期抽奖中 3 你可以获得不同种类的偶像,1 每次会话费用 需要 500 。 第
- 2 期抽奖中 这是第 1 个偶像是闲人 5 ,出现的概率是 20% 。
- 2 期抽奖中 这是第 2 个偶像是闲人 1 ,出现的概率是 30% 。
- 2 期抽奖中 这是第 3 个偶像是闲人 2 ,出现的概率是 50% 。
- 通过此输入,2 每次抽奖能够获得的偶像都是不同的。
- 1 《Tsume no Kuji》的花费金额为 6015.789473684 、2 《Tsume no Kuji》的花费金额为 3327.380952381 所以,一起 9343.17042606516 就是答案。
入力例 2
3 3 1 10 1 100 1 10 2 100 1 10 3 100
出力例 2
30
- 1 第抽奖, 每2 第抽奖, 每3 期抽奖 1 每次拉动即可收集所有偶像。
入力例 3
1 1 1 1000 1 100
出力例 3
1000
- 偶像与抽奖 1由于每人只有一张,我就去玩彩票。 1 次即可。
入力例 4
2 2 2 1000 1 30 2 70 2 800 1 80 2 20
出力例 4
2128.57142857143
入力例 5
3 3 2 50 1 99 2 1 3 300 1 90 2 9 3 1 3 3000 1 80 2 15 3 5
出力例 5
30333.4291970656