802. Where the Cubic Crosses

A reservoir holds f(x) = a*x^3 + b*x^2 + c*x + d litres when the gate is open x centimetres, for x between 0 and 100. The coefficients satisfy a >= 1 and b, c, d >= 0, so f strictly increases across the whole range.

Given a target y with d < y <= f(100), print the opening x with f(x) = y, to exactly 6 digits after the decimal point.

a=1 b=0 c=0 d=0, y = 8 -> 2.000000 a=1 b=0 c=0 d=0, y = 2 -> 1.259921 a=1 b=2 c=3 d=4, y = 1000 -> 9.269081 a=1 b=0 c=0 d=0, y = 1000000 -> 100.000000

## Why the formula is the wrong tool here

Cardano's method solves a cubic in closed form. It is long, it needs care with the sign of the discriminant, and on the way it takes cube roots of numbers that may be negative, which several library pow functions refuse. Every line of it is a chance to be wrong.

The search below is five lines and does not care what degree the polynomial has. Swap the cubic for a fifth-degree polynomial, or for x + sin(x), and only the evaluation changes.

## Why the predicate is monotone, argued rather than asserted

Take 0 <= x1 < x2 <= 100. Then x1^3 < x2^3 and x1^2 <= x2^2 and x1 < x2, all because cubing and squaring preserve order on non-negative numbers. With a >= 1 strictly positive and b, c >= 0,

f(x2) - f(x1) = a*(x2^3 - x1^3) + b*(x2^2 - x1^2) + c*(x2 - x1) > 0

so f is strictly increasing and f(x) <= y is true on an initial stretch and false after it.

## The bounds

lo = 0 and hi = 100 come straight from the statement, and the guarantee d < y <= f(100) means the crossing is inside that interval. No search for a bound is needed, which is rare in this topic and worth noticing.

## Evaluating without losing digits

Use Horner's form:

f(x) = ((a*x + b)*x + c)*x + d

Three multiplications and three additions, no powers, and the intermediate values stay as small as they can. Writing a*x*x*x + b*x*x + c*x + d costs more operations and loses more of the last digits.

## The boundary that breaks a careless implementation

A target barely above d. Then x is small and a*x^3 is tiny next to d, so the sum a*x^3 + d can round to exactly d in floating point and the predicate reports "still too small" for a whole stretch of candidates. The constraint d < y keeps y - d at least 1, which is what makes the search safe; the test with a = 100 and y = 1 sits at that edge.

## Related problems

Problem 801 is this search with a bare power instead of a polynomial, and problem 810 replaces the polynomial with a sum of fractions whose upper bound has to be worked out rather than given.

## Cost

Time O(100). Space O(1).

Constraints - `1 ≤ a ≤ 100` - `0 ≤ b ≤ 100` - `0 ≤ c ≤ 100` - `0 ≤ d ≤ 100` - `d < y ≤ a * 10^6 + b * 10^4 + c * 100 + d` - every answer is at least `10^-9` away from a halfway rounding point at 6 digits