Score : $475$ points

问题描述

设有 $N$ 个轮盘赌。第 $i$ 个（$1\leq i\leq N$）轮盘上有 $P_i$ 个整数 $S_{i,1}$、$S_{i,2}$、…、$S_{i,P_i}$，玩一次需要支付 $C_i$ 日元。当你玩第 $i$ 个轮盘一次时，会从 $1$ 到 $P_i$（包含两端）之间均匀随机选择一个整数 $j$，然后你将获得 $S_{i,j}$ 分。

各个轮盘上获得的分数独立于以往的结果。

高桥希望至少获得 $M$ 分。他将采取行动以尽量减少他在至少获得 $M$ 分之前所支付的金额。每次玩过后，他可以根据先前的结果来选择接下来要玩哪个轮盘。

求高桥在至少获得 $M$ 分前预期需要支付的金额。

更正式的定义

以下是更为正式的问题陈述。对于高桥可以选择的某个轮盘策略，按照该策略，在至少获得 $M$ 分之前他所支付的预期金额 $E$ 定义如下：

• 对于自然数 $X$，令 $f(X)$ 表示根据该策略，高桥在至少获得 $M$ 分或总共玩了 $X$ 次轮盘之前预期支付的金额。令 $E=\displaystyle\lim_{X\to+\infty}f(X)$。

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ roulette wheels. The $i$-th $(1\leq i\leq N)$ wheel has $P _ i$ integers $S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i}$ written on it, and you can play it once by paying $C _ i$ yen. When you play the $i$-th wheel once, an integer $j$ between $1$ and $P _ i$, inclusive, is chosen uniformly at random, and you earn $S _ {i,j}$ points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least $M$ points. Takahashi will act to minimize the amount of money he pays before he earns at least $M$ points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least $M$ points.

More formal definition

Here is a more formal statement. For a strategy that Takahashi can adopt in choosing which wheel to play, the expected amount of money $E$ that he pays before he earns at least $M$ points with that strategy is defined as follows.

• For a natural number $X$, let $f(X)$ be the expected amount of money Takahashi pays before he earns at least $M$ points or plays the wheels $X$ times in total according to that strategy. Let $E=\displaystyle\lim _ {X\to+\infty}f(X)$.

Under the conditions of this problem, it can be proved that $\displaystyle\lim _ {X\to+\infty}f(X)$ is finite no matter what strategy Takahashi adopts. Find the value of $E$ when he adopts a strategy that minimizes $E$.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print the expected amount of money Takahashi will pay until he earns at least $M$ points in a single line. Your output will be considered correct when the relative or absolute error from the true value is at most $10 ^ {-5}$.

Sample Input 1

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

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

• Pay $50$ yen to play roulette $2$ and earn $S _ {2,4}=8$ points.
• Pay $50$ yen to play roulette $2$ and earn $S _ {2,1}=1$ point.
• Pay $100$ yen to play roulette $1$ and earn $S _ {1,1}=5$ points. He has earned a total of $8+1+5\geq14$ points, so he quits playing.

In this case, he pays $200$ yen before earning $14$ points.

Your output will be considered correct when the relative or absolute error from the true value is at most $10 ^ {-5}$, so outputs such as 215.9112 and 215.9155 would also be considered correct.

Sample Input 2

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

Sample Output 2

60

It is optimal to keep spinning roulette $2$ until you get $100$ points.

Sample Input 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

Sample Output 3

45037.072314895291126319493887599716

update @ 2024/3/10 08:58:47