← 返回题目列表

AtCoder · arc016_3

C. 社交游戏

中文机器翻译题面 查看原题

問題文

高桥喜欢收集偶像的卡牌游戏。
在这个游戏中,通过支付金钱和抽签,你可以赢得由一定概率分布决定的偶像。 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. 1 行中,一个整数表示空闲总数。 N(1≦N≦10),代表彩票类型的整数 M(1≦M≦4)由半角空格分隔。 来自行
  2. 2 行之后 i(1≦i≦M) 有关抽奖的信息以半角空格分隔。
    • 整数 C_i (1≦C_i≦N) 是 代表第i 次抽签中包含的偶像数量。 代表抽取第
    • 整数 cost_i (1≦cost_i≦3000) 是 代表第i 张彩票所需的价格。
  3. 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. 1 期抽奖中 2 你可以获得不同种类的偶像,1 每次会话费用 需要 300 。 第
      • 1 期抽奖中 这是第 1 个偶像是闲人 3 ,出现的概率是 5% 。
      • 1 期抽奖中 这是第 2 个偶像是闲人 4 ,出现的概率是 95% 。
    2. 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