PROG0138 - Birthday paradox

Determine the probability $p_n$ that, in a group of $n$ randomly chosen people, some of them will have the same birthday. If we assume that each day of the year (we exclude February 29) is equally probable for a birthday, the probability that none of the people in the group have the same birthday is given by $$ q_n = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-n+1}{365} $$ The probability $p_n$ is then computed as $p_n = 1-q_n$. For the probability $p_n \in \mathbb{R}$, it always applies that $0 \leq p_n \leq 1$.

Note: The above formula is only valid for $n \leq 365$. What happens if $n>365$?

Note: By the pigeonhole principle, the probability reaches 100% when the number of people reaches 366 (since there are 365 possible birthdays, excluding February 29). However, 99% probability is reached with just 57 people, and 50% probability with 23 people. This is called the birthday paradox, not because it is a paradox in the sense of leading to a logical contradiction, but because the mathematical truth contradicts naive intuition. An intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but the birthday problem demonstrates that this is not the case.

Input

No input.

Output

For each value $n$ that is between 5 and 75 (boundaries included) and that is a multiple of five print the value $n$ itself, a single space, and then the probability $p_n$ that in a group of $n$ people at least two people have the same birthday. Use a separate line every time.

Example

5 0.0271355736998
10 0.116948177711
15 0.252901319764
...
75 0.999719878174

Bepaal de kans $p_n$ dat in een groep van $n$ personen minstens twee personen op dezelfde dag verjaren. De kans dat geen twee personen op dezelfde dag verjaren, wordt gegeven door $$ q_n = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \cdot \frac{365-n+1}{365} $$ De kans $p_n$ bekomt men dan uiteraard als $p_n = 1-q_n$. Voor de kans $p_n \in \mathbb{R}$ geldt steeds dat $0 \leq p_n \leq 1$.

Opmerking: Bovenstaande formule werkt enkel wanneer $n \leq 365$. Wat gebeurt wanneer $n>365$?

Opmerking: Dit wordt de verjaardagsparadox genoemd, omdat deze kans groter is dan wat de meeste mensen intuïtief zouden verwachten.

Invoer

Geen invoer.

Uitvoer

Schrijf voor elke waarde van $n$ tussen 5 en 75 (grenzen inbegrepen) die een vijfvoud is op een afzonderlijke regel: de waarde van $n$, één enkele spatie, en vervolgens de kans $p_n$ dat in een groep van $n$ personen minstens twee personen op dezelfde dag verjaren.

Voorbeeld

5 0.0271355736998
10 0.116948177711
15 0.252901319764
...
75 0.999719878174

Added by:Peter Dawyndt
Date:2011-08-08
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.