# PROBLEM LINK: Chintu Ki Press

# DIFFICULTY:

Medium

# PREREQUISITES:

Binary search , Maths

# PROBLEM:

You are given **M** printers and time taken by each printer to print one page is also given. You have to find minimum time required to print total **P** pages, given more than one printer can work simultaneously.

# QUICK EXPLANATION:

We can find answer by doing binary search over all the possible answers i.e over the space T \in [1 , 10^{18} ].

# EXPLANATION:

Firstly, since more than one printer can work simultaneously therefore working on all M printers simultaneously will always be optimal.

Using the constraints we can find the range of answer **T** .

Minimum time to print **P** pages can be **T = 1s** and maximum time can be **T = 10^{18}s** (*each printer can take maximum 10^9s to print one page and maximum number of pages to be print i.e. P can also be 10^9 so T \leq 10^{18}s )* .

Now, Take ** l = 1** and ** r = 10^{18} ** and perform binary search on the space [l , r] .

Take T = mid be your answer and calculate total number of pages all M printers can print in time T **i.e. sum = \displaystyle\sum_{i = 0}^{m-1} \left\lfloor\frac{T}{t_i}\right\rfloor ** .

if sum \geq P, it means time **T** is sufficient to print **P** pages and it can be minimized if possible hence our search space becomes [l , mid - 1] .

On the other hand if sum < P, it means time **T** is insufficient to print **P** pages and thatâ€™s why we will search in upper half i.e. [mid + 1 , r] .

Repeating above steps until l \leq r, we will get the minimum time **T** recquired to print **P** pages.

Time-Complexity: O(M*log S) , where S = 10^{18}.

# SOLUTIONS:

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll m, p;
ll a[200005];
bool check(ll time)
{
ll i, s = 0;
for (i = 0; i < m; i++)
{
s += (time / a[i]);
if (s >= p)
return true;
}
if (s >= p)
return true;
else
return false;
}
int main()
{
ll i, j, k, ans = 1e18 + 1;
cin >> m >> p;
for (i = 0; i < m; i++)
cin >> a[i];
ll l = 1, r = 1e18;
while (l <= r)
{
ll mid = (l + r) / 2;
if (check(mid))
{
r = mid - 1;
ans = min(ans, mid);
}
else
l = mid + 1;
}
cout << ans << endl;
return 0;
}
```