TwoLotteryGames
SRM 418 · 2008-09-20 · by ltdtl
SRM 418 · 2008-09-20 · by ltdtl · Math, Simple Math
Problem Statement
Problem Statement
Yesterday, when you were passing by the newsstand near your home, you saw an advertisement for lottery games. The advertisement said "Choose m different numbers between 1 and n, inclusive. We will also randomly pick m different numbers between 1 and n, inclusive, and if you have at least k numbers in common with us, you win!".
You want to know the probability of winning this lottery game. You are given three integers n, m, and k as described above. Return the probability of winning the game.
Notes
- Your return must have relative or absolute error less than 1E-9.
Constraints
- n will be between 2 and 8, inclusive.
- m will be between 1 and n-1, inclusive.
- k will be between 1 and m, inclusive.
Examples
0)
3 2 1 Returns: 1.0
Here you and the organizers will choose 2 numbers among 3. It will be 4 numbers in total, so at least 1 number in your and their sets will repeat for sure.
1)
3 1 1 Returns: 0.3333333333333333
Now you and the organizers will choose 1 number. These numbers will be the same with probability 1/3.
2)
8 2 1 Returns: 0.4642857142857143
3)
8 4 2 Returns: 0.7571428571428571
4)
8 3 1 Returns: 0.8214285714285714
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TwoLotteryGames with a public method double getHigherChanceGame(int n, int m, int k) · 90 test cases · 2 s / 256 MB per case