Jackpot
Time limit1sMemory limit512 MB
Choose how many of n doors to open first so that the probability of picking the prize times the reduced prize is largest; output that best expected payout.
- Level
Medium7 of 10
- Topics
- Math, Binary search, Greedy, Probability
- Solved
- No attempts yet
Problem
The thunderingly fun new game show 'Jackpot' has bounded onto television screens up and down the land and is the next big thing. It runs on a simple premise. There are a number of doors, behind one of which is hidden a monetary prize and behind all of the others of which are hidden goats. Each contestant chooses how many doors will be opened before they pick a door to look at. The prize decreases as each door is opened. If they open the door and find the money, they get to keep it.
Not content with guessing, you have decided to work out the best number of doors to open to maximise your expected profit, where expected profit is the probability of winning multiplied by the remaining prize fund.
You have found out that the remaining prize fund PR is a function of the initial prize fund m, the number of doors opened d and a scaling factor f, that is,
PR = m − (d · f)2
Given the number of doors, initial prize fund and the scaling factor, can you work out how many doors should be opened before you try to pick a door to maximise your expected profit?
Input
One line of input containing:
- One integer n (1 ≤ n ≤ 1018), the number of doors.
- One integer m (1 ≤ m ≤ 1018), the initial prize fund.
- One floating point f (0 < f ≤ 1), the scaling factor.
There will always be only one door with the best value.
Output
One line containing:
- One floating point number, the value of the expected payout.
The output must be accurate to an absolute or relative error of at most 10−6.