Gem Island

Time limit3sMemory limit1024 MB

Summary

At each of d steps a uniformly random gem splits in two; find the expected total held by the r largest holders after d splits.

Level: Hard8 of 10
Topics: Probability, Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Gem Island is a tiny island in the middle of the Pacific Ocean. Until recently it was known as one of the poorest and most peaceful places on Earth. Today it is neither poor nor peaceful. What happened?

One sunny morning, not too long ago, all inhabitants of Gem Island woke up to a surprise. Each of them was holding one sparkling gem. The gems had appeared overnight by magic. Everybody was suddenly rich, everybody could finally afford the things they had dreamed of, and the name of the island made much more sense.

The next morning one of the inhabitants woke up to another surprise. Her gem had split into two gems. The same thing happens on every night that follows: exactly one of the gems on the island, picked uniformly at random among all gems there, splits into two.

After a while the inhabitants held widely varying numbers of gems. A few had a lot and many had only a few. How come some inhabitants had more gems than others? Did they cheat, were they just lucky, or was something else at work?

The island elders have asked for your help. They want you to determine whether pure chance explains the uneven distribution of gems. If it does, tensions on the island drop a great deal.

The island has $n$ inhabitants. You are to determine the gem distribution after $d$ nights of gem splitting. The value of interest is the expected number of gems held together by the $r$ people with the largest numbers of gems. Stated precisely, suppose that after $d$ nights the numbers of gems held by the $n$ inhabitants are sorted in non-increasing order as $a_1 \ge a_2 \ge \cdots \ge a_n$ . What is the expected value of $a_1 + \cdots + a_r$ ?

Input

The first line contains three integers $n$ , $d$ and $r$ separated by spaces ( $1 \le n, d \le 500$ , $1 \le r \le n$ ).

Output

Print the expected number of gems held by the top $r$ inhabitants after $d$ nights, rounded to exactly nine digits after the decimal point. Pad with zeros so that all nine digits are always printed. If the expected value lies exactly halfway between two candidates, round it up.

Examples3

Example 1
Input
```
2 3 1
```
Expected output
```
3.500000000
```
Example 2
Input
```
3 3 2
```
Expected output
```
4.900000000
```
Example 3
Input
```
5 10 3
```
Expected output
```
12.256743257
```