Casino

Time limit2sMemory limit256 MB

Summary

With m dollars, a goal of n dollars and win chance p percent per play, pick each stake to maximize the chance of reaching the goal.

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

Problem

Taro owes a debt of $n$ dollars. To pay it he goes to a casino, where he names a bet before each play. A bet is an integer amount of at least $1$ dollar and never exceeds the money he holds at that moment. He wins a play with probability $p$ percent, and a win pays him the same amount again, so his money grows by the bet. A loss takes the bet away.

Taro holds $m$ dollars now and may repeat the play as many times as he wants. He pays the whole debt once his money reaches $n$ dollars or more.

Find the maximum probability that Taro pays the whole debt, and find every optimum first bet. An amount is an optimum first bet if placing it on the first play and then playing as well as possible still reaches that maximum probability.

Input

The first line contains three integers $p$ , $m$ , and $n$ separated by single spaces ( $0 \le p \le 100$ , $0 < m < n \le 10^9$ ).

Output

Print three lines.

The first line contains the maximum probability that Taro pays the whole debt, rounded to exactly six digits after the decimal point.

The second line contains the number of optimum first bets.

The third line contains all optimum first bets in ascending order separated by single spaces when that number is at most $200$ . When the number is greater than $200$ , the third line contains the $100$ smallest optimum first bets and the $100$ largest ones, in ascending order and separated by single spaces.

Examples2

Example 1
Input
```
60 2 3
```
Expected output
```
0.789474
1
1
```
Example 2
Input
```
25 3 8
```
Expected output
```
0.109375
2
1 3
```