G - Doubles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個のサイコロがあります。 i 番目のサイコロは K_i 個の面をもち、各面にはそれぞれ A_{i,1},A_{i,2},\ldots,A_{i,K_i} が書かれています。このサイコロを振ると、各面がそれぞれ \frac{1}{K_i} の確率で出ます。

あなたは N 個のサイコロから 2 個を選んで振ります。サイコロを適切に選んだときの、2 つのサイコロの出目が等しくなる確率の最大値を求めてください。

制約

  • 2 \leq N \leq 100
  • 1 \leq K_i
  • K_1+K_2+\dots+K_N \leq 10^5
  • 1 \leq A_{i,j} \leq 10^5
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
K_1 A_{1,1} A_{1,2} \dots A_{1,K_1}
\vdots
K_N A_{N,1} A_{N,2} \dots A_{N,K_N}

出力

答えを出力せよ。真の解との相対誤差または絶対誤差が 10^{-8} 以下のとき正解とみなされる。

入力例 1

3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6

出力例 1

0.333333333333333
  • 1 番目のサイコロと 2 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{3} です。
  • 1 番目のサイコロと 3 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{6} です。
  • 2 番目のサイコロと 3 番目のサイコロを選んで振ったとき、出目が等しくなる確率は \frac{1}{6} です。

よって最大値は \frac{1}{3}=0.3333333333\ldots となります。

入力例 2

3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2

出力例 2

0.666666666666667

Score : 400 points

Problem Statement

There are N dice. The i-th die has K_i faces, with the numbers A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} written on them. When you roll this die, each face appears with probability \frac{1}{K_i}.

You choose two dice from the N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq K_i
  • K_1 + K_2 + \dots + K_N \leq 10^5
  • 1 \leq A_{i,j} \leq 10^5
  • All input values are integers.

Input

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

N
K_1 A_{1,1} A_{1,2} \dots A_{1,K_1}
\vdots
K_N A_{N,1} A_{N,2} \dots A_{N,K_N}

Output

Print the answer. Your answer is considered correct if the absolute or relative error from the true solution does not exceed 10^{-8}.

Sample Input 1

3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6

Sample Output 1

0.333333333333333
  • When choosing the 1st and 2nd dice, the probability that the outcomes are the same is \frac{1}{3}.
  • When choosing the 1st and 3rd dice, the probability is \frac{1}{6}.
  • When choosing the 2nd and 3rd dice, the probability is \frac{1}{6}.

Therefore, the maximum probability is \frac{1}{3} = 0.3333333333\ldots.

Sample Input 2

3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2

Sample Output 2

0.666666666666667