Minimum Polynomial Threshold

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 32M

Problem type

Fred has a rocket! He wants the rocket to fly high, but doesn't the rocket to consume too much fuel. Knowing the various relevant concepts in physics, chemistry, and biology, he has deduced that the maximum height of the rocket is the result of a cubic polynomial \text{height} = h(x) = Ax^3+Bx^2+Cx, where x is the fuel setting on the rocket booster. Furthermore, you can assume that A,B,C\ge 1, as a higher rocket booster setting always corresponds to higher height. Of course, a higher rocket booster setting will result in more fuel being consumed, so Bob wants you to find the minimum booster setting (value of x) such that the maximum height (value of h(x)) is at least H. Do note that x must be nonnegative.

For this problem, using double precision float pointing numbers (double in java and c++) is recommended


1\le A,B,C\le 10^6

0<H\le 10^{24}

Input Specification

The first line contains 4 decimal values, corresponding to A, B, C, and H, respectively.

Output Specification

One line with one decimal value, the minimum value of x such that Ax^3+Bx^2+Cx\ge H. Your answer will be regarded as correct if its absolute value from the accepted answer is less than or equal to 10^{-4}

Sample Input

1 2 3 6

Sample Output


Sample Explanation

x=1 is the minimum value such that 1\cdot x^3+2x^2+3x\ge 6


There are no comments at the moment.