Problem J
Weightlifting
In competitive weightlifting, you must perform a sequence of lifts. You have a constant strength $s$, and a decreasing energy reserve $e$. For each lift, you may choose any positive (not necessarily integer) weight $w$ to attempt. If $s \ge w$, the lift succeeds and your energy goes down by $e_{\text {success}}$; if $s < w$, the lift fails and your energy goes down by $e_{\text {failure}}$. You may continue attempting lifts as long as $e > 0$. If at any point $e \le 0$, you can make no further attempts. Your score is the maximum weight you successfully lift or $0$ if every attempt failed.
Ideally, you should lift exactly at your strength limit. However, you do not know your strength $s$. You only know that you can definitely lift the empty bar ($25\text { kg}$), and that the maximum conceivable lift is $225\text { kg}$. How close to an optimal score can you guarantee? That is, what’s the smallest $d$ for which you can ensure a score of at least $s-d$?
For example, suppose $e = 4$, $e_{\text {success}} = 1$ and $e_{\text {failure}} = 2$. You try to lift $200\text { kg}$ and fail. Now, $e = 2$. You try $100\text { kg}$ and succeed. Now, $e = 1$. You try $150\text { kg}$ and succeed. Now, $e = 0$ and you must stop. You know that you can lift $150\text { kg}$, but you cannot lift $200\text { kg}$. Your strength $s$ must be somewhere between $150\text { kg}$ and $200\text { kg}$. You scored $150$, your optimal score might be as high as (just under) $200$. You still don’t know $s$, but you know you’re within $50$. In this case, $d = 50$.
That’s a specific example, and the strategy used is certainly not optimal. You can do better. What’s the smallest value of $d$ you can get so that you can guarantee a score of at least $s-d$ for any and all possible values of $s$?
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input consists of a single line with $3$ space-separated integers $e$, $e_{\text {success}}$, $e_{\text {failure}}$ ($1 \le e, e_{\text {success}}, e_{\text {failure}} \le 10^7$) where $e$ is your beginning energy reserve, $e_{\text {success}}$ is the amount of energy expended in a successful lift, and $e_{\text {failure}}$ is the amount of energy expended in a failed lift.
Output
Output a single line with a real number $d$, which is the minimum weight in $\text {kg}$ such that you can ensure a score of at least $s-d$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
1 3 3 |
112.5 |
Sample Input 2 | Sample Output 2 |
---|---|
12 3 3 |
13.333333333333334 |
Sample Input 3 | Sample Output 3 |
---|---|
3000 2 3 |
2.0E-8 |