Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### beginner_610's blog

By beginner_610, history, 16 months ago, This problem was asked in online round to my friend.I am not able to get how to approach the problem using which technique, if someone could help me?, Thanks.

# Problem:

****Alice has decided to publish X different comic books.****

****For this Purpose , He has Y printing machines and Z binding machines.****

****The ith printing machine takes print[i] minutes to print all pages of a comic book. Each binding machine takes K minutes to bind all the pages of a comic book.**

****At a single point of time ,each machine(a printing or a binding) can process at most the pages of a single comic book.**

****For publishing comic books , these steps have to be followed.**

****1. An unoccupied printing machine i starts printing the pages of a comic book.**

****2. After print[i] minutes , the printed pages are taken out of the ith printing machine.**

****3. After non-negative amount of time , the printed pages of comic book are placed in an unoccupied binding machine.**

****4. After K minutes, the pages are taken out of the binding machine.**

****Assume that the time is negligible for placing the pages into or removing from the machines.**

****You need to help alice , find out the minimum time in order to publish X comics.**

## Input:

1.first line consists of the no of testcases.

2.Second line consists of X,Y,Z,K.

3.Y space separted integers which denote the printing time print[i] of ith printing machine.

### OUTPUT:

For each test case , print the minimum time to publish all X comics. Constraints:

1<=t<=10

1<=X<=10^6

1<=Y<=10^5

1<=Z<=10^9

1<=K<=10^9

1<=print[i]<=10^9

Sample Test Cases:

input:

3

2 1 1 34

1100

2 3 2 10

10 16 1

3 2 2 5

5 7

output:

2234

12

15 Comments (20)
 » Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » You can check here, some points may be useful.
•  » » No , like from where to start?
•  » » » is it to be done with dp , or some binary search
•  » » » » From reading it looks like binary search, has a role to play. Sort the print[i] array then apply binary search. This will give us the minimum time for printing comics, but it will not include the binding time.
•  » » » » » Bro can you try to code it and run the given testcases, i wasnt able to code it.
•  » » » » » May i know why the binary search is used for?
•  » » Can anyone help please? , or its just for people with higher ratings?
•  » » » help please, just have 2 min to give this a read
 » This is just a weird variation of IOI Job Processing. Maybe looking at that sol will help you.
•  » » Sir , can you help me with its code? , i wasnt able to code it and the given test cases didnt work
 » 12 months ago, # | ← Rev. 3 →   Hey I recently came across this question and implemented a solution with time complexity O(xLog(x)+yLog(y)+zLog(z)) so basically the time complexity is nLog(n) where n = max(x,y,z); Ideone Solution Link Feel Free to comment in case you have any doubt. #include using namespace std; int main() { int test; cin>>test; while(test--) { int x,y,z,k,i; cin>>x>>y>>z>>k; vectorvec(y); vectorprinted; for(int i=0;i>vec[i]; sort(vec.begin(),vec.end()); priority_queue,vector>,greater>>pq; int currtime = 0; i=0; int j=0; while(ivec[j]) { pq.push(make_pair(vec[j],j)); ++j; ++i; } else { int currtime=pq.top().first; int currmachine=pq.top().second; printed.push_back(currtime); pq.pop(); pq.push(make_pair(currtime+vec[currmachine],currmachine)); ++i; } } } while(!pq.empty()) { printed.push_back(pq.top().first); pq.pop(); } i=0; vectorfinalvec; for(i=0;i
•  » » Bro can you explain a bit , what your pq, printed and finalvec are storing?
•  » » Your code is not correct. 1 2 2 2 1 2 3 Answer should be 4, but this code outputs 5.  if(jvec[j]) { pq.push(make_pair(vec[j],j)); ++j; ++i; } Here is the mistake. If you selected 2, then instead of selecting 3 it will select 2.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   This gives the correct answer. #include using namespace std; #define ll long long int long minTime(vector machines, ll goal) { ll s=1; ll e=machines*goal; while(s=goal) break; } if(temp>=goal) { e=m; } else{ s=m+1; } } return e; } int main() { int test; cin>>test; while(test--) { ll x,y,z,k,i; cin>>x>>y>>z>>k; vectorvec(y); ll currtime = 0; vectorprinted; for(int i=0;i>vec[i]; sort(vec.begin(),vec.end()); ll mnTime=minTime(vec,x); for(auto xx : vec) { ll temp=xx; while(temp<=mnTime) { printed.push_back(temp); temp+=xx; } } sort(printed.begin(),printed.end()); i=0; vector ans; priority_queue ,greater > pq; for(i=0;i
•  » » » » You can check my code in the below comment. It is much simpler and intuitive.
 » Imagine if the question was to calculate if it's possible to publish X books in a given time t, this can be solved by considering all printing machines and binding machines. Now you just have to binary search for the time t
 » This question can be solved greedily. - In a set(multiset to be specific), the printing finish time will be stored for each printing machine. Initially, all printing machines will be available so if we take any machine its ending time will be the time it takes to print a book. Suppose we take 1st machine with time 5, then if we take it next time its task will end at 10. So, we will replace the finishing time for 1st machine to be 10. - Similar logic is used for binding machine's job.Here is my code. #include using namespace std; using ll = long long int; void solve() { int x, y, z, k; cin >> x >> y >> z >> k; multiset> print; for(int i=0, t; i> t; print.insert({t, t}); } multiset bound; for(int i=0; ifirst; t = print.begin()->second; print.erase(print.begin()); print.insert({cur+t, t}); ans = max(cur, *bound.begin())+k; bound.erase(bound.begin()); bound.insert(ans); } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int _t; cin >> _t; while(_t--) solve(); }