AT_abc314_e [ABC314E] 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}$ 分。

每次轮盘获得的分数相互独立。

高桥君想要获得至少 $M$ 分。高桥君会采取使得在获得至少 $M$ 分之前所支付金额尽可能小的策略。并且，高桥君每次玩轮盘时，可以根据之前所有轮盘的结果选择下一次要玩的轮盘。

请计算高桥君在获得至少 $M$ 分之前所支付金额的期望值。

更严格地说，定义如下。对于每一种高桥君选择轮盘的策略，按照该策略，在获得至少 $M$ 分或玩了 $X$ 次轮盘之前所支付金额的期望为 $f(X)$，则 $E=\displaystyle\lim_{X\to+\infty}f(X)$。

可以证明，在本题条件下，无论高桥君采取何种策略，$\displaystyle\lim_{X\to+\infty}f(X)$ 都是有限的。请输出当高桥君采取使 $E$ 最小的策略时，$E$ 的值。

输入格式

输入按以下格式从标准输入给出。

$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

输入 #1

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

输出 #1

215.913355350494384765625

输入输出样例 #2

输入 #2

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

输出 #2

60

输入输出样例 #3

输入 #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

说明/提示

约束条件

• $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}>0\ (1\leq i\leq N)$
• 输入均为整数

样例解释 1

例如，高桥君可以按如下方式玩轮盘：

• 支付 $50$ 日元玩第 $2$ 台轮盘，获得 $S_{2,4}=8$ 分。
• 支付 $50$ 日元玩第 $2$ 台轮盘，获得 $S_{2,1}=1$ 分。
• 支付 $100$ 日元玩第 $1$ 台轮盘，获得 $S_{1,1}=5$ 分。此时获得的总分为 $8+1+5\geq 14$，因此结束。
  在这个例子中，获得 $14$ 分共支付了 $200$ 日元。只要输出的值与真实值的相对误差或绝对误差不超过 $10^{-5}$，如 215.9112 或 215.9155，都可以判定为正确。

样例解释 2

一直玩第 $2$ 台轮盘直到获得 $100$ 分是最优策略。

由 ChatGPT 4.1 翻译