시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 9 | 7 | 7 | 77.778% |
Gunnar and his friends like games which involve rolling dice. Gunnar has a huge collection of 6-sided, 12-sided and 20-sided dice. All the games with dice started to bore him, so he came up with a new game. He rolls an s-sided die n times and wins if at least k different numbers appear in the n throws. An s-sided die contains s distinct numbers 1, . . . , s on its sides.
Since this is a game only for one person, Gunnar and his friends decided to make it more fun by letting other people bet on a particular game. Before you bet on a particular game, you would like to know how probable it is to throw at least k different numbers in n throws with an s-sided die. We assume that all numbers have the same probability of being thrown in each throw.
The input consists of a single line with three integers n, s, and k (1 ≤ n ≤ 10 000, 1 ≤ k ≤ s ≤ 500). n is the number of throws, k the number of different numbers that are needed to win and s is the number of sides the die has.
Output one line with the probability that a player throws at least k different numbers within n throws with an s-sided die. Your answer should be within absolute or relative error at most 10−7.
3 3 2
0.888888889
3 3 3
0.222222222
Contest > KTH Challenge > KTH Challenge 2016 D번