/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
偏りのない 6 面さいころが N 個あり、i 番目のさいころ (1 \leqq i \leqq N) の j 番目の面 (1 \leqq j \leqq 6) には整数 A_{i,j} が書かれている。
高橋君は、1 個のさいころを選んで 1 回振る、という操作を繰り返す。ただし、2 回目以降の操作で、前回の操作で出た目より小さいか同じ目が出てしまったら、操作をやめる。各回にどのさいころを振るかは、前回に出た目を見てから選ぶことができる。
高橋君は、できるだけさいころを多く振りたいと考えている。操作が行われる回数の期待値が最大化されるような選択が行われたときの操作回数の期待値を求めよ。
制約
- 1 \leqq N \leqq 30,000
- 1 \leqq A_{i,j} \leqq {10}^{9}
- A_{i,j} はすべて異なる。
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1, 5} A_{1, 6}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2, 5} A_{2, 6}
:
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N, 5} A_{N, 6}
出力
操作回数の期待値を表す実数を出力せよ。ジャッジの出力との絶対誤差または相対誤差が 10^{-6} 以下であれば正解と判定される。
入力例 1
2 1 2 3 4 5 6 7 8 9 10 11 12
出力例 1
3.64925355954377
入力例 2
3 12 237 374 111 247 234 857 27 98 65 83 90 764 60 999 11 7 4
出力例 2
3.42188884244970
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have N unbiased six-sided dice. The j-th face (1 \leq j \leq 6) of the i-th die (1 \leq i \leq N) has an integer A_{i,j} written on it.
Takahashi repeats the following operation: choose a die and toss it. However, in the second and subsequent operations, if the die shows a number that is less than or equal to the number shown in the previous operation, the process ends. The die to toss each time can be chosen after seeing the previous number shown.
Takahashi wants to toss a die as many times as possible. Find the expected number of operations done when the choices are made to maximize this number.
Constraints
- 1 \leq N \leq 30000
- 1 \leq A_{i,j} \leq {10}^{9}
- A_{i,j} are all different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1, 5} A_{1, 6}
A_{2,1} A_{2,2} A_{2,3} A_{2,4} A_{2, 5} A_{2, 6}
:
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N, 5} A_{N, 6}
Output
Print a real number representing the expected number of operations done. Your output is considered correct if the absolute or relative error from the judge's output is at most 10^{-6}.
Sample Input 1
2 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 1
3.64925355954377