AT_abc314_e [ABC314E] Roulettes

[problemUrl]: https://atcoder.jp/contests/abc314/tasks/abc314_e $ N $ 台のルーレットがあります。 $ i $ 番目 $ (1\leq\ i\leq\ N) $ のルーレットには $ P\ _\ i $ 個の整数 $ S\ _\ {i,1},S\ _\ {i,2},\ldots,S\ _\ {i,P\ _\ i} $ が書かれており、$ C\ _\ i $ 円支払うことで $ 1 $ 回プレイできます。 $ i $ 番目のルーレットを $ 1 $ 回プレイすると、$ 1 $ 以上 $ P\ _\ i $ 以下の整数 $ j $ が一様ランダムに選ばれ、$ S\ _\ {i,j} $ ポイントを得ることができます。 ルーレットで得られるポイントは、過去の結果と独立に決まります。 高橋くんは、ポイントを $ M $ ポイント以上獲得したいです。 高橋くんは、$ M $ ポイント以上獲得するまでに支払う金額をなるべく小さくするように行動します。 ただし、高橋くんはルーレットをプレイするたびこれまでのルーレットの結果を見て次にプレイするルーレットを選ぶことができます。 高橋くんがポイントを $ M $ ポイント以上獲得するまでに支払う金額の期待値を求めてください。 より厳密な定義より厳密には、次のようになります。 高橋くんがルーレットを選ぶ戦略を決めるごとに、その戦略で $ M $ ポイント以上獲得するまでに支払う金額の期待値 $ E $ が次のように定義されます。 - 自然数 $ X $ に対して、その戦略に従って高橋くんが $ M $ ポイント以上獲得するか、ルーレットを $ X $ 回プレイするまでに支払う金額の期待値を $ f(X) $ とする。$ E=\displaystyle\lim\ _\ {X\to+\infty}f(X) $ とする。 この問題の条件のもとで、高橋くんがどのような戦略をとっても $ \displaystyle\lim\ _\ {X\to+\infty}f(X) $ が有限の値になることが証明できます。 高橋くんが $ E $ を最小にするような戦略をとったときの $ E $ の値を求めてください。

N/A

N/A

### 制約 - $ 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) $ - 入力はすべて整数 ### Sample Explanation 1 例えば、高橋くんはルーレットを次のようにプレイすることができます。 - $ 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` などと出力しても正解になります。 ### Sample Explanation 2 $ 100 $ ポイントが出るまでルーレット $ 2 $ を回し続けるのが最適です。