Murthal Parantha-Divide and Conquer

#1

ques-The coding blocks members went to the success party of their first ever online boot-camp at Murthal. They ordered P number of paranthas. The stall has L cooks and each cook has a rank R. 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). Calculate the minimum time needed to cook all the paranthas.

Input Format:
First line contains P, the number of pratha ordered. In the next line the first integer denotes the number of cooks L and L integers follow in the Next line each denoting the rank of a cook.
Output Format
Print an integer which tells the number of minutes needed to get the order done.

Sample Input
10
4
1 2 3 4
Sample Output
12

I am not able to understand the test cases.
how we got the output as 12 ?

#2

in 1st 10 min rank 1 will make 4 paratha.
in 1st 12 minute rank 2 will make 3 paratha
in 1st 9 minute rank 3 will make 2 paratha
in 1st 4 minute rank 4 will make 1 paratha.
total min time for 10 = 12 min.

#3

I am not able to figure out the approach in order to solve this question ?

#4

use binary search… if not familiar with such problem i would suggest suggest you to do some binary search Q first…

#5

how will binary search, help in this? it’s a greedy question

#6

its a binary search Q… thats why i told you to get familar with binary search Q first…bdw in binary search check() function we use greedy appoarch…

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.