TopCoder problem "LotteryPyaterochka" used in SRM 466 (Division I Level Two)



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.
 

Definition

    
Class:LotteryPyaterochka
Method:chanceToWin
Parameters:int
Returns:double
Method signature:double chanceToWin(int N)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10863

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14150&pm=10863

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Simple Math