1317. Birthdays

Рожь. 1878. Пейзаж стал классическим и программным произведением, как для самого художника, так и для художественной критики его времени. На одном из эскизов к картине И.И. Шишкин сделал запись, которую можно считать его творческим кредо: «Раздолье, простор, угодье, рожь, Божья благодать, русское богатство».

Лирическое отношение к отечественной природе, воспетое И.И. Шишкиным, было ярко выражено в стихах Н.А. Некрасова:

Все рожь кругом, как степь живая,

Ни замков, ни морей, ни гор.

Спасибо, сторона родная,

За твой врачующий простор.

It is known that in a group of 23 or more people, the probability that at least two of them share the same birthday (day and month) exceeds 50%. This fact may seem paradoxical, since the probability of a single person being born on a specific day of the year is very small, and the probability that two people share a birthday is even smaller. However, the result is confirmed by probability theory. Therefore, this fact is not a paradox in the strict scientific sense — there is no logical contradiction. The paradox lies only in the discrepancy between our intuition and the result of the mathematical calculation.

Given a number of people, calculate the probability that at least two of them share the same birthday. Assume that a year has 365 days.

Input. Each line represents a separate test and contains the number of people n (1 < n < 400).

Output. For each value of n, print on a separate line the probability (in percent) that at least two of the n people share the same birthday (day and month). Print the probability with 8 digits after the decimal point.

Sample input	Sample output
2 10 23 366	0.27397260% 11.69481777% 50.72972343% 100.00000000%

SOLUTION

probability

Algorithm analysis

First, let’s compute the probability that in a group of n people all birthdays are distinct. If n is greater than 365, then by the pigeonhole principle this probability is zero. If n does not exceed 365, we reason as follows.

We choose the first person and note his birthday. Then we choose the second person: the probability that his birthday does not coinside with the first person’s birthday is 1 – 1 / 365. For the third person, the probability that his birthday does not coinside with the birthdays of the first two people is 1 – 2 / 365.

Continuing this reasoning, for the last person the probability that their birthday does not coinside with the birthdays of all the previous ones is 1 – (n – 1) / 365.

Multiplying all these probabilities, we obtain the probability that all birthdays in the group are different:

Then, the probability that at least two people out of n share the same birthday is equal to one minus the probability that all birthdays are distinct:

Algorithm implementation

In the array p[i] we’ll store the corresponding probability values p(i).

double p[401];

Let p[1] = 1. The remaining values of the array p[i] are computed using the formula given in the problem analysis.

p[1] = 1.0;

for (i = 2; i < 401; i++)

p[i] = p[i-1] * (1.0 - (i - 1.0) / 365);

For each input value n, compute the corresponding probability and print the result.

while (scanf("%d",&n) == 1)

printf("%.8lf%%\n",(1 - p[n]) * 100);