시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 17 | 13 | 4 | 80.000% |
Bytica works in the biological expedition. Now she got $n$ colored foxes for experiments. There's a problem, however: foxes of the same color are absolutely indistinguishable.
Now Bytica wants to mark the foxes with colored labels. She repeats the following steps until each pair of foxes becomes distinguishable:
Each procedure (three steps) takes exactly one minute.
Two foxes are considered to be distinguishable if their colors differ or sets of colors of their labels differ.
The only thing Bytica is unsure about now is the expected time before all foxes will be pairwise distinguishable. So she asked you to write a program to compute this value.
Input consists of two lines. The first line contains two integers $n$ and $k$ ($1 \le k < n \le 30$). The second line contains $n$ integers, the $i$-th integer describes the initial color of the $i$-th fox.
Colors are denoted by positive integers not exceeding $1000$.
Print one real number: the expected time in minutes before each pair of foxes becomes distinguishable. Your answer will be considered correct if its relative or absolute error is within $10^{-6}$.
2 1 20 20
1.000000
2 1 15 1000
0.000000