NearBirthdays
TCO05 Finals · 2005-08-16 · by Yarin
Problem Statement
If more than 23 people are selected at random, the chance that two of them have birthdays on the same day is more than 50%. While this may sound counterintuitive, it is fairly easy to verify that this indeed is the case. Furthermore, only 14 people are needed for there to be more than a 50% chance that at least two of them have birthdays within one day of each other.
Create a class NearBirthdays containing the method probability which calculates the probability
that at least two people among noPeople have birthdays within withinDays days (inclusive)
of each other.
The method should take as input an
Notes
- The last day of a year is within one day of the first day of a year.
- A solution will be judged correct if the absolute error is less than 1e-9.
Constraints
- noPeople will be between 2 and 100, inclusive.
- withinDays will be between 0 and 100, inclusive.
- daysInAYear will be between 100 and 1000, inclusive.
2 99 200 Returns: 0.995
If the first person's birthday is on day 1 in the 200 day long year, the only time the second person's birthday isn't within 99 days is if he has a birthday on day 101. Hence the probability that both persons have birthdays within 99 days of each other is 199/200 = 0.995.
30 0 365 Returns: 0.7063162427192686
This is a typical school class version: in a school class with 30 people, the likelihood that two of them are born on the same day is roughly 70%.
6 6 500 Returns: 0.33373900738431983
5 100 199 Returns: 1.0
100 0 1000 Returns: 0.9940410733677595
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NearBirthdays with a public method double probability(int noPeople, int withinDays, int daysInAYear) · 60 test cases · 2 s / 256 MB per case