Problem AL
Ticket Lottery

Picture in Public Domain via Wikimedia Commons
You and your friends are in New York and are planning to go see a broadway musical. Unfortunately, New York being New York, the tickets are just a tiny bit expensive. But one of the shows has a ticket lottery each night where impecunious people such as yourself have a chance to win the right to buy slightly less expensive tickets to good seats.

The lottery operates as follows. First, everyone interested enters the lottery. Then, $n$ lucky winners are drawn, and each of these is offered to buy up to $t$ tickets.

Given the number of people $p$ in your group (all of which entered the lottery) and the total number of people $m$ that entered the lottery, what is the probability that you will be able to get tickets for your entire group? Assume that the $n$ lucky winners are chosen uniformly at random from the $m$ people that entered the lottery, and that each person can win at most once.


The input consists of a single line containing four integers:

  • $1 \le m \le 1000$: the total number of people who entered the lottery.

  • $1 \le n \le m$: the total number of winners drawn.

  • $1 \le t \le 100$: the number of tickets each winner is allowed to buy.

  • $1 \le p \le m$: the number of people in your group.


Output a single line containing the probability that your entire group can get tickets to the show. This probability should be given with an absolute error of at most $10^{-9}$.

Sample Input 1 Sample Output 1
100 10 2 1
Sample Input 2 Sample Output 2
100 10 2 2
Sample Input 3 Sample Output 3
10 10 5 1

Please log in to submit a solution to this problem

Log in