Painting Pips
Time limit1sMemory limit1024 MB
Given N dice and M total pips to distribute across faces, find the maximum expected product of the rolled values.
- Level
Hard8 of 10
- Topics
- Math, Dynamic programming, Greedy, Probability
- Solved
- No attempts yet
Problem
Alice and Bob like playing games. Lately they have been playing a game in which Alice rolls dice and Bob pays her a dollar amount equal to the product of the numbers rolled on the dice. But for lack of the required skill, Alice and Bob have grown bored.
To spice things up, they decide to use a custom set of dice. Specifically, Alice has blank -sided dice and she gets to paint pips on them. She has enough paint to paint pips. Subject to this constraint, she can paint the dice however she wants; for example, she may paint more than pips on one side of a die. Note that she can choose to paint pips on a side; if any of the rolled numbers is , the product is .
Assuming Alice paints the dice optimally, what is the expected value of her winnings in this game?
Input
The only line of input contains two space-separated integers, () and (): the number of dice in the game and the maximum number of pips Alice may paint in total, respectively.
Output
Output a single real number, Alice's expected winnings. Your answer is considered correct if its absolute or relative error is at most .
Notes
In the first sample case, the best Alice can do is to put one pip on each die. This gives her an expected value of .
In the second sample case, one optimal strategy for Alice is to put a pip on each side of the die. No matter what she rolls, she receives a payout of .
In the final sample case, Alice can only paint pip, so no matter what she does, she will always receive a payout of .