803. Ropes Cut to One Real Length
A chandler has n ropes; rope i is a[i] centimetres long. They must be cut into at
least k pieces, all of exactly the same length, and that length does NOT have to be a whole
number of centimetres. Leftovers are thrown away and pieces may not be joined.
Print the greatest length one piece can have, to exactly 6 digits after the decimal point.
ropes 802 743 457 539, k = 11 -> 200.500000
ropes 5 5 5, k = 7 -> 1.666667
ropes 1 1, k = 3 -> 0.500000
At 200.5 the four ropes yield 4, 3, 2 and 2 pieces, which is 11 exactly. At 201 they yield 3, 3, 2 and 2, which is only 10.
## The partner problem, and the one line that changes
Problem 765 asks this with the length required to be a whole number, and there the answer is an integer binary search ending on a seam between two integers. Here the seam is a real number, and that single change matters more than it looks:
- the integer version can afford
lo < hiand stop when they meet; this one cannot, and runs a - fixed 100 halvings instead
- the integer version's answer is
200, this one's is200.5, so the two problems have - genuinely different answers on the same input
- the integer version never divides; here
a[i] / Lis a real division whose floor is the piece - count, and that floor is where the whole subtlety lives
Solve 765 first if you have not. Then notice how little of the code survives.
## Why the predicate is monotone
The number of pieces of length L cut from a rope of length a is floor(a / L). Dividing by a
larger L gives a smaller quotient, and flooring preserves that, so every term of
pieces(L) = floor(a[0] / L) + floor(a[1] / L) + ... + floor(a[n-1] / L)
falls or stays as L rises. The lengths that yield at least k pieces therefore form an initial
stretch, and the answer is where that stretch ends.
## The bounds
lo = 0.
hi = sum(a) / k. Even with no waste at all the total length cannot produce k pieces longer
than the average, so nothing above that can work. Using max(a) also works and is looser.
The answer is never tiny: taking L = max(a) / k already yields k pieces from the longest rope
alone, so the answer is at least 1 / 10^4, comfortably printable at 6 decimals.
## The boundary that breaks a careless implementation
The exact division. When L divides a exactly, floor(a / L) should be a / L and not one
less. In a real binary search the candidate almost never lands exactly on such a value, which is
precisely why a FIXED iteration count matters more than an exact tie rule: the loop converges to
the seam from both sides and the printed digits are decided long before any tie could occur.
The second is the piece count overflowing. With ropes of 10^6 and L near zero the count is
astronomical, so stop adding as soon as the running total reaches k.
## Related problems
Problem 765 is the whole-number twin named above. Problem 804 is the same counting argument with areas instead of lengths, and problem 797 is the integer mirror where the count is of gaps rather than pieces.
## Cost
Time O(100 * n). Space O(n).
Constraints - `1 ≤ n ≤ 10000` - `1 ≤ k ≤ 10000` - `1 ≤ a[i] ≤ 10^6` - 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 k.
The second line contains n integers a[0] ... a[n-1], the rope lengths in centimetres.
Output
Print the greatest possible piece length in centimetres 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.