810. The Pressure That Delivers the Flow
A manifold has n valves. At pressure x, valve i passes
a[i] * x / (x + b[i])
litres per minute. Every valve sees the same pressure, and the total must come to exactly F
litres per minute.
Print the pressure x that achieves it, to exactly 6 digits after the decimal point.
one valve a=10 b=1, F = 5 -> 1.000000
one valve a=10 b=100, F = 1 -> 11.111111
two valves a=5 b=1 twice, F = 6 -> 1.500000
## Why the function is monotone
Rewrite one term as
a*x / (x + b) = a - a*b / (x + b)
As x grows, x + b grows, so a*b / (x + b) shrinks, so the term grows. Every term grows,
so the total grows, and total(x) < F is true on an initial stretch and false after it. That is
the predicate.
The same rewriting shows something the search needs: each term is always BELOW a[i] and
approaches it without ever reaching it. The total has a ceiling of sum(a) that it never touches.
## The real difficulty: there is no obvious upper bound
In most problems in this topic hi falls out of the story, some value at which everything
trivially works. Here the function has a horizontal asymptote, so as F approaches sum(a) the
required pressure runs off to infinity, and no constant is right for every input. A bound has to
be DERIVED.
Write S = sum(a) and B for the largest b[i], which is at most 1000. Since
x + b[i] <= x + B, every term satisfies a[i]*x / (x + b[i]) >= a[i]*x / (x + B), so
total(x) >= S * x / (x + B)
At x = 10^4 that lower bound is S * 10^4 / (10^4 + 1000), which is about 0.909 * S. The
constraint on F caps it at 0.9 * S, so total(10^4) is certainly at least F and
hi = 10^4 always works.
That is the lesson: the constraint given on F is not decoration, it is exactly what makes a
finite bound exist, and reading it that way is the skill.
## Fixed iterations, never an epsilon
One hundred halvings of [0, 10^4] leave an interval of about 10^-26, far below what a double
can represent, so the loop is exact to the type and always finishes. A
while (hi - lo > 1e-9) loop on this range risks never terminating once the two ends become
neighbouring doubles.
## The boundary that breaks a careless implementation
F = 1 with a single small valve. The answer can be well under 1, as in the third sample list
above where a ratio of 1 / 99 comes out at 0.010101, so a search that starts lo at 1
instead of 0 misses it entirely.
## Related problems
Problem 802 searches a polynomial whose range is handed to you, which is the case this problem removes. Problem 801 is the same fixed-iteration skeleton on a pure power.
## Cost
Time O(100 * n). Space O(n).
Constraints - `1 ≤ n ≤ 1000` - `1 ≤ a[i] ≤ 100` - `1 ≤ b[i] ≤ 1000` - `sum of a[i] ≥ 2` - `1 ≤ F ≤ (9 * sum of a[i]) / 10`, using integer division - every answer is at least `10^-9` away from a halfway rounding point at 6 digits
Input
The first line contains two integers n and F.
Each of the next n lines contains two integers a[i] and b[i], describing one valve.
Output
Print the pressure with exactly 6 digits after the decimal point, in plain fixed notation and never in exponent form, alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.