Factory Machines

Explanation

Here, we are given n machines that takes certain seconds each to make a single product. We need to find the minimum time required to make t products. It is given that the machines can work simultaneously.

We can use binary search to find the minimum time required. And we can calculate the number of products for a given time using the following formula: time / machine1 + time / machine2 + ... + time / machinen >= t

Code

# Be sure to submit the Python code as PyPy3, otherwise it will give TLE.

n, target = map(int, input().split())
machines = list(map(int, input().split()))

low = 1
high = min(machines) * target

while high >= low:
    mid = (low + high) // 2
    total = sum(mid // m for m in machines)
    if total >= target:
        high = mid - 1
    else:
        low = mid + 1

print(int(low))