PRATA - Roti Prata

no tags 

IEEE is having its AGM next week and the president wants to serve cheese prata after the meeting. The subcommittee members are asked to go to food connection and get P(P<=1000) pratas packed for the function. The stall has L cooks(L<=50) and each cook has a rank R(1<=R<=8). A cook with a rank R can cook 1 prata in the first R minutes 1 more prata in the next 2R minutes, 1 more prata in 3R minutes and so on(he can only cook a complete prata) ( For example if a cook is ranked 2.. he will cook one prata in 2 minutes one more prata in the next 4 mins an one more in the next 6 minutes hence in total 12 minutes he cooks 3 pratas in 13 minutes also he can cook only 3 pratas as he does not have enough time for the 4th prata). The webmaster wants to know the minimum time to get the order done. Please write a program to help him out.



The first line tells the number of test cases. Each test case consist of 2 lines. In the first line of the test case we have P the number of prata ordered. In the next line the first integer denotes the number of cooks L and L integers follow in the same line each denoting the rank of a cook.


Print an integer which tells the number of minutes needed to get the order done.




4 1 2 3 4
1 1
8 1 1 1 1 1 1 1 1

hide comments
aj54: 2019-12-24 15:41:37

Binary Search and AC in one go!

scorpy1: 2019-09-13 18:09:59

AC with Binary Search

aayush_b1999: 2019-08-03 22:56:35

let max_rank=(the max rank in the given array)
let p=number of prata req.
upper_limit=(p*(2*max_rank+(p-1)*max_rank))/2 (sum of p terms in ap)

amit125992: 2018-12-29 11:22:08

Last edit: 2018-12-29 11:31:47
yaseenmollik: 2018-11-11 18:26:25

Had to learn Min Heap and Priority Queue just to solve this. And finally ac :)

Last edit: 2018-11-11 18:26:43
rajat_123: 2018-11-01 11:55:55

Set upper limit as 10000007 in Java, it gives TLE with 10^9 :)

ompr_07: 2018-10-04 19:22:49

Binary Search AC in one go!!

codeinfinity: 2018-10-02 20:16:28

I agree with @pallindromeguy
you should take upper limit quite high

hvr81070: 2018-09-03 21:10:11

#40 :)

nadstratosfer: 2018-03-16 18:20:48

shadow10, the cooks' finishing time for each prata:
1 - 1, 3, 6, 10
2 - 2, 6, 12
3 - 3, 9
4 - 4, 12
--> 10th (and 11th) prata served at minute 12.

Another problem that could be fun to play with but is ruined by idiotic time limit. Get formula to use in BS to get AC and don't waste time inventing your own algo because you won't get to see how it performs anyway. Why build a comprehensive testfile if one can set TL so low that a Py3 program doing nothing can't pass?

Last edit: 2018-03-16 21:35:32

Added by:Saransh Bansal
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem- NTU IEEE codejam 2011