Roulettes

题目描述

有 $N$ 个转盘。 第 $i$ 个 $(1\leq i\leq N)$ 转盘上写着 $P _ i$ 个整数 $S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i}$，你可以通过支付 $C _ i$ 日元来玩一次它。 当你玩第 $i$ 个转盘一次时，会从 $1$ 到 $P _ i$（含）之间均匀随机地选择一个整数 $j$，你获得 $S _ {i,j}$ 点数。 各转盘获得的点数与过去的结果相互独立。 Takahashi 想至少获得 $M$ 点数。 Takahashi 将采取使他在获得至少 $M$ 点数之前所支付的钱最小化的行动。 在每次游玩之后，他可以根据之前的结果选择下一次要玩哪个转盘。 求 Takahashi 在获得至少 $M$ 点数之前预期会支付的金额。

输入格式

输入按照标准输入给出，格式如下： $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}$

输出格式

在一行中打印 Takahashi 在获得至少 $M$ 点数之前将会支付的期望金额。 当你的输出与真实值的相对误差或绝对误差不超过 $10 ^ {-5}$ 时，将被视为正确答案。

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

215.913355350494384765625

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

60

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

45037.072314895291126319493887599716

提示

$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)$ 所有输入值均为整数。例如，Takahashi 可以如下玩转盘。

支付 $50$ 日元来玩转盘 $2$ 并获得 $S _ {2,4}=8$ 点。 支付 $50$ 日元来玩转盘 $2$ 并获得 $S _ {2,1}=1$ 点。 支付 $100$ 日元来玩转盘 $1$ 并获得 $S _ {1,1}=5$ 点。他总共获得了 $8+1+5\geq14$ 点，所以他停止游玩。

在这种情况下，他在获得 $14$ 点之前支付了 $200$ 日元。 当你的输出与真实值的相对误差或绝对误差不超过 $10 ^ {-5}$ 时，将被视为正确答案，因此诸如 $215.9112$ 和 $215.9155$ 的输出也将被视为正确。
最优策略是不断旋转转盘 $2$ 直到你得到 $100$ 点。

标签: AtCoder|abc314E

来源

AtCoder|abc314E