LotteryPyaterochka
SRM 466 · 2009-11-12 · by Chmel_Tolstiy
SRM 466 · 2009-11-12 · by Chmel_Tolstiy · Dynamic Programming, Simple Math
Problem Statement
Problem Statement
Alice likes lotteries. Her favorite lottery is Pyaterochka, which is very popular in Belarus. Each ticket in this lottery is a rectangular grid with N rows and 5 columns, where each cell contains an integer between 1 and 5*N, inclusive. All integers within a single ticket are distinct.
After the tickets are distributed, the lottery organizers randomly choose 5 distinct integers, each between 1 and 5*N, inclusive. Each possible subset of 5 integers has the same probability of being chosen. These integers are called the winning numbers. A ticket is considered a winner if and only if it has a row which contains at least 3 winning numbers.
Alice will buy a single ticket. Each possible ticket has the same probability of being sold. Return the probability that she will buy a winning ticket.
After the tickets are distributed, the lottery organizers randomly choose 5 distinct integers, each between 1 and 5*N, inclusive. Each possible subset of 5 integers has the same probability of being chosen. These integers are called the winning numbers. A ticket is considered a winner if and only if it has a row which contains at least 3 winning numbers.
Alice will buy a single ticket. Each possible ticket has the same probability of being sold. Return the probability that she will buy a winning ticket.
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- N will be between 1 and 100, inclusive.
Examples
0)
1 Returns: 1.0
Any ticket contains just one line with some permutation of numbers 1, 2, 3, 4, 5. Ony one set of winning numbers is possible - {1, 2, 3, 4, 5}. So the only line of any ticket contains all 5 winning numbers, and therefore each ticket is a winner.
1)
2 Returns: 1.0
For any set of winning numbers chosen, there's exactly one line in any ticket that contains at least 3 winning numbers.
2)
3 Returns: 0.5004995004995004
3)
6 Returns: 0.13161551092585574
4)
100 Returns: 4.7998099843704644E-4
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LotteryPyaterochka with a public method double chanceToWin(int N) · 100 test cases · 2 s / 256 MB per case