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.
Hard9ProbabilityDynamic programmingMathNo attempts yetTime limit2sMemory limit256 MBTaro 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.
The first line contains three integers p, m, and n separated by single spaces (0≤p≤100, 0<m<n≤109).
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.