| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 24 | 14 | 13 | 68.421% |
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:
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.
2 1 1
-0.001191480807419
7 1 1 2 1 3 1 1
-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번