752. Catching the Last Connection

A journey has n legs; leg i is d[i] kilometres long. Every leg runs at the same whole speed s kilometres per hour.

Legs depart on the hour. After finishing a leg you wait for the next departure, so a leg that takes d / s hours actually consumes ceil(d / s) hours of the day. The LAST leg is different: nothing is waited for afterwards, so it consumes exactly d / s hours, fraction included.

You must arrive within T minutes. Print the smallest whole speed that manages it, or -1 if no speed does.

legs 1 3 2, T = 162 minutes -> 3 legs 1 3 2, T = 90 minutes -> -1 legs 5 5 5 5, T = 240 minutes -> 5 leg 100000, T = 1 minute -> 6000000

At speed 3 the first two legs cost 1 hour each and the last costs 2/3 of an hour, which is 2.6667 hours, inside the 2.7 hours allowed. At speed 2 the first two cost 1 and 2 hours, already over.

## Do not use floating point

The natural check adds ceil(d[i] / s) for the first n - 1 legs and then d[n-1] / s, and compares the total against T / 60. Written with doubles it is wrong on exactly the inputs that matter: the answer sits where the total EQUALS the limit, and that is where a rounding error of one part in 10^16 decides the comparison the wrong way.

Multiply the comparison out instead. With S for the whole-hour part,

S + d[n-1] / s <= T / 60

becomes, after multiplying both sides by 60 * s (positive, so the direction is kept),

60 * s * S + 60 * d[n-1] <= T * s

Every term is now an integer and the check is exact.

## Why the predicate is monotone

Raising s cannot raise ceil(d / s) for any leg, and it strictly lowers d[n-1] / s. So the total travel time is non-increasing in s, and once a speed arrives in time every faster speed does as well. Feasible speeds form a suffix of 1, 2, 3, ..., so the first feasible one can be found by binary search.

## The bound that catches everyone

hi = max(d) is WRONG here, and it is the whole lesson of this problem.

At any s >= max(d) each of the first n - 1 legs already costs its minimum of one hour, so raising the speed further only shortens the last leg. The condition becomes

s * (T - 60 * (n - 1)) >= 60 * d[n-1]

and when the bracket is as small as it can be while still positive, namely 1, the speed has to reach 60 * d[n-1]. With distances up to 10^5 that is 6 * 10^6, sixty times larger than max(d).

So lo = 1 and hi = 6 * 10^6. Test hi before searching: if even that fails, print -1.

## When the answer is -1

The first n - 1 legs cost at least one hour each whatever the speed, and the last leg costs something strictly positive. So no speed can finish in 60 * (n - 1) minutes or fewer, which is why 1 3 2 with T = 120 also answers -1 and not 1. Checking hi once covers every such case without a separate rule.

## Overflow

T * s reaches 10^7 * 6 * 10^6 = 6 * 10^13, and 60 * s * S reaches about 3.6 * 10^13. Both need 64 bits. A 32-bit product here wraps to a negative number, which compares as "in time" and makes the search return a speed far too low.

## Related problems

Problem 751 is the same rounding with a single deadline and no fractional leg. Problem 248 warns off sqrt() for the same reason this problem warns off division in doubles.

## Cost

Time O(n log(6 * 10^6)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ T ≤ 10^7` - `1 ≤ d[i] ≤ 100000`