← 返回题目列表

AtCoder · abc314_e

H. 轮盘赌

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

分数: 475 点

问题陈述

有 N 轮盘赌轮。 的 i-th (1\leq i\leq N) 轮子有 上面写着 P _ i 整数 S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} ,付费可以玩一次 C _ i 日元。 当您播放 i-第轮一次,整数 j 之间 1 和 P _ i,含在内,随机统一选择,您赚取 S _ {i,j} 点。

您从轮盘中获得的积分与过去的成绩无关。

高桥想要至少赚到 M 点。 高桥会采取行动,在他至少赚到钱之前,尽量减少他支付的金额 M 点。 每次玩完后,他可以根据之前的结果选择下一个玩哪个轮盘。

求出高桥在至少赚到钱之前将支付的预计金额 M 点。

更正式的定义

这是更正式的声明。 对于高桥在选择玩哪个轮盘时可以采取的策略,期望的金额 E 他至少在赚钱之前付款 该策略的 M 点定义如下。

  • 对于自然数 X,让 f(X) 是高桥在他至少赚到钱之前支付的预期金额 M 指向或转动轮子 根据该策略,总共 X 次。让 E=\displaystyle\lim _ {X\to+\infty}f(X).

在该问题的条件下,可以证明 无论高桥采取什么策略, \displaystyle\lim _ {X\to+\infty}f(X) 都是有限的。 求出 的值 E 当他采取最小化策略时 E.

约束

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
  • 1\leq P _ i\leq 100\ (1\leq i\leq N)
  • 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
  • \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

输出

打印高桥将支付的预期金额,直到他至少赚到 M 点在一行中。 当与真实值的相对或绝对误差最大时,您的输出将被认为是正确的 10 ^ {-5}.


示例输入 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

示例输出 1

215.913355350494384765625

例如,Takahashi 可以按如下方式玩轮子。

  • 支付 50 日元玩轮盘赌 2 并赚取 S _ {2,4}=8 点。
  • 支付 50 日元玩轮盘赌 2 并赚取 S _ {2,1}=1 点。
  • 支付 100 日元玩轮盘赌 1 并赚取 S _ {1,1}=5 点。他总共获得了 8+1+5\geq14 点,所以他退出了游戏。

在这种情况下,他支付 200 赚取前日元 14 点。

当与真实值的相对或绝对误差最大时,您的输出将被认为是正确的 10 ^ {-5},因此输出如 215.9112 和 215.9155 也将被认为是正确的。


示例输入 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

示例输出 2

60

继续旋转轮盘赌是最佳选择 2 直到你得到 100 点。


示例输入 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

示例输出 3

45037.072314895291126319493887599716