### beginner_610's blog

By beginner_610, history, 5 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

• +5

 » 5 months ago, # |   0 Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).
 » 5 months ago, # |   +12 You can check here, some points may be useful.
•  » » 5 months ago, # ^ |   0 No , like from where to start?
•  » » » 5 months ago, # ^ |   0 is it to be done with dp , or some binary search
•  » » » » 4 months ago, # ^ |   0 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.
•  » » » » » 4 months ago, # ^ |   0 Bro can you try to code it and run the given testcases, i wasnt able to code it.
•  » » 5 months ago, # ^ |   0 Can anyone help please? , or its just for people with higher ratings?
•  » » » 4 months ago, # ^ |   0 help please, just have 2 min to give this a read
 » 4 months ago, # |   0 This is just a weird variation of IOI Job Processing. Maybe looking at that sol will help you.
•  » » 4 months ago, # ^ |   0 Sir , can you help me with its code? , i wasnt able to code it and the given test cases didnt work
 » 4 weeks ago, # | ← Rev. 3 →   0 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
•  » » 12 days ago, # ^ |   0 Bro can you explain a bit , what your pq, printed and finalvec are storing?
 » 12 days ago, # |   0 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