시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 1 1 1 100.000%

문제

The Birthday Paradox is the name given to the surprising fact that if there are just $23$ people in a group, there is a greater than $50\%$ chance that a pair of them share the same birthday. The underlying assumptions for this are that all birthdays are equally likely (which isn't quite true), the year has exactly $365$ days (which also isn't true), and the people in the group are uniformly randomly selected (which is a somewhat strange premise).  For this problem, we'll accept these assumptions.

Consider what we might observe if we randomly select groups of $P=10$ people. Once we have chosen a group, we break them up into subgroups based on shared birthdays. Among many other possibilities, we might observe the following distributions of shared birthdays:

  • all $10$ have different birthdays, or
  • all $10$ have the same birthday, or
  • $3$ people have the same birthday, $2$ other people have the same birthday (on a different day), and the remaining $5$ all have different birthdays.

Of course, these distributions have different probabilities of occurring.

Your job is to calculate this probability for a given distribution of people sharing birthdays.  That is, if there are $P$ people in a group, how probable is the given distribution of shared birthdays (among all possible distributions for $P$ people chosen uniformly at random)?

입력

The first line gives a number $n$ where $1 \le n \le 365$. The second line contain integers $c_1$ through $c_n$, where $1 \le c_i \le 100$ for all $c_i$. The value $c_i$ represents the number of people who share a certain birthday (and whose birthday is distinct from the birthdays of everyone else in the group).

출력

Compute the probability $b$ of observing a group of people with the given distribution of shared birthdays. Since $b$ may be quite small, output instead $\log_{10}(b)$. Your submission's answer is considered correct if it has an absolute or relative error of at most $10^{-6}$ from the judge's answer.

예제 입력 1

2
1 1

예제 출력 1

-0.001191480807419

예제 입력 2

7
1 1 2 1 3 1 1

예제 출력 2

-4.310614508857128

힌트

The first sample case shows $P=2$ people with distinct birthdays. The probability of this occurring is $b = 364/365 \approx 0.9972602740$, and $\log_{10}(b) \approx -0.001191480807419$.

The second sample case represents the third example in the list given earlier with $P=10$ people. In this case, the probability is $b \approx 0.0000489086$, and $\log_{10}(b) \approx -4.310614508857128$.

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2019 G번

  • 문제를 만든 사람: Greg Hamerly