753. Minutes Until the Trips Are Done

A depot runs n shuttles. Shuttle i takes t[i] minutes for one round trip and starts a new one the instant it returns, so by minute T it has completed T / t[i] trips, rounded DOWN. Shuttles do not help each other and do not queue.

Print the earliest minute at which the depot has completed at least trips round trips in total.

shuttles 1 2 3, trips = 5 -> 3 shuttles 2 5, trips = 10 -> 15 shuttles 3 3 3, trips = 6 -> 6 shuttles 3 3 3, trips = 7 -> 9

At minute 3 the three shuttles have completed 3, 1 and 1 trips, which is 5. At minute 2 they have 2, 1 and 0, which is 3.

## Why counting minute by minute is too slow

The count at a given minute is a one-line sum:

done(T) = T / t[0] + T / t[1] + ... + T / t[n-1] (integer division)

but the answer can be as large as 10^14, so walking T = 1, 2, 3, ... is hopeless even though each step is cheap.

## Why the predicate is monotone

Integer division by a fixed positive number is non-decreasing in its numerator: if T <= T2 then T / t <= T2 / t. Every term of done therefore grows or stays as T grows, so done is non-decreasing, and a minute that reaches the target is followed only by minutes that also reach it. The answers read no no no YES YES ... and the answer is the first YES.

Notice what is NOT needed: the shuttle times do not have to be sorted, and there is no array to search. The thing being searched is the minute itself.

## The bounds

lo = 1. A single minute can already be enough when a shuttle takes one minute.

hi = min(t) * trips. The fastest shuttle on its own completes trips trips by then, so that minute certainly qualifies, and the answer cannot be later. Using max(t) * trips also works and is needlessly loose; using sum(t) or 10^9 does not work at all.

## The boundary that breaks a careless implementation

Two of them.

First, the count is bigger than it needs to be. Stop adding the moment the running count reaches trips. That is a SPEED fix, not an overflow fix, and the difference is worth getting right.

T never rises above hi = min(t) * trips, and every shuttle has t[i] >= min(t), so each term obeys T / t[i] <= T / min(t) <= trips and the whole untrimmed sum is at most n * trips = 10^5 * 10^7 = 10^12. A signed 64-bit integer reaches 9223372036854775807, over nine million times larger, so nothing here wraps. Note also that the two alarming extremes exclude each other: a shuttle taking 1 minute drags hi down to trips, at most 10^7, so the 10^14 end of the range and the one-minute shuttle never appear in the same input.

What the untrimmed sum actually costs is time, 10^5 divisions on each of the roughly 47 search steps in cases where the first two or three shuttles already settle the question.

Second, the seam. When 3 3 3 is asked for 6 trips the answer is 6, not 7 or 5. An implementation that moves hi = mid - 1 on a successful candidate loses the answer whenever the target is met exactly. On success the correct move is hi = mid, keeping the candidate in play.

## Overflow

min(t) * trips reaches 10^7 * 10^7 = 10^14, which needs 64 bits before the search even begins. Computing it in 32-bit arithmetic and then widening is the classic way to get this wrong: the multiplication has already wrapped.

## Related problems

Problem 757 is the same count with a one-off setup cost per worker, which changes the bound and adds a boundary that this problem does not have. Problem 758 replaces the constant rate with one that slows down as the worker goes on.

## Cost

Time O(n log(min(t) * trips)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ trips ≤ 10^7` - `1 ≤ t[i] ≤ 10^7`