TLE '17 Contest 3 P4 - Meatballs

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Mama mia! That's a spicy meatball-a!

Fax McClad, Croneria's hungriest bounty hunter, is about to participate in the annual Cronerian Thanksgiving Meatball Contest! There are N participants, including Fax, numbered from 1 to N.

The contest will consist of N-1 elimination rounds. Each round, the remaining participants line up in order of their number. Suppose there are x people in the current round. Then, they will be given a total of x+K meatballs on a plate, one of which is very spicy.

The participant at the front of the line eats a single meatball from the plate, without replacement. If they eat the spicy meatball, then they are eliminated, and the next round begins. If they do not eat the spicy meatball, they go to the back of the line, and the next participant at the front of the line goes up to eat. The process continues until the spicy meatball has been eaten. After the last round, there is only one participant remaining. That participant is declared the winner.

Fax wants the grand prize of the contest, one million moneys, so he can do more weapons research. If Fax is participant number i, what is the probability that he will win?


For all subtasks:

1 \le N

0 \le K

1 \le i \le N

Subtask Points N K
1 5 N = 4 K \le 1
2 15 N \le 10 K \le 20
3 20 N \le 100 K \le 10^3
4 40 N \le 10^3 K \le 10^6
5 20 N \le 10^5 K \le 2

Input Specification

The only line of input will consist of 3 space-separated integers, N, K, and i.

Output Specification

On a single line, output a real number, the probability that Fax will win the contest. Your answer will be judged correct if its relative error does not exceed 10^{-6}. It is recommended to output in scientific notation (most languages should support this).

Sample Input 1

4 0 2

Sample Output 1


Sample Input 2

5 1 3

Sample Output 2



There are no comments at the moment.