| Submit | All submissions | Best solutions | Back to list |
PRATA - Roti Prata |
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.
Input
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.
Output
Print an integer which tells the number of minutes needed to get the order done.
Example
Input:
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1
Output:
12
36
1
| Added by: | Saransh Bansal |
| Date: | 2011-05-14 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own problem- NTU IEEE codejam 2011 |
hide comments
|
||||||||||||
|
2022-02-21 18:30:47
If for python 3 you occasionally get tle use Python 2 (PyPy 2.7.13) , syntax is almost similar. Although for this question Python 3 works just fine, maybe you are doing something wrong. As a suggestion I would say for each mid time in outer search space, use AP quadratic formula to calculate the potential number of parathas don't use 2 nested loops even though in constraints it says L <= 50. For python 2 take care of float division. Last edit: 2022-02-21 18:34:06 |
||||||||||||
|
2021-12-24 14:45:17
The reason answer for first use case P = 10, R[] = [1,2,3,4], Ans = 12 is: 1. Let's take answer as 10 so: * first will make (1+2+3+4 = 10min) i.e. 4Prata * Second will make (2 + 4 = 6min) i.e. 2Prata. Note we cannot take 3rd prata time as total time will become 2 + 4 + 6 = 12min in that case * Third will make (3 + 6 = 9min) i.e. 2 Prata * Fourth will make (4min) i.e. 1Prata So if time = 10 then Prata = 4 + 2 + 2 + 1 = 9 Prata And similarly to make 10Prata min time will be 12min |
||||||||||||
|
2021-10-25 18:15:31
beatrock why are you taking the rank 4 cook two times the starting four means that there are four cooks see input |
||||||||||||
|
2021-09-11 17:39:00
why we need 12 min in 1st example? we can do it in 10 1 will cook 4 in 10 min 2 will cook 2 in 6 min 3 will cook 2 in 9 min 4s will cook 1 each in 4 min 4+2+2+1+1 = 10 Ohh understod first integer indicates the no of cooks so here 4 in not the rank of cook rather it is no of cook Last edit: 2021-09-11 17:44:40 |
||||||||||||
|
2021-09-05 09:52:22
great question |
||||||||||||
|
2021-08-14 13:23:18
what will be the max required time in worst case...??? Last edit: 2021-08-14 13:23:44 |
||||||||||||
|
2021-07-20 18:54:56
why we need 12 min in 1st example? we can do it in 10 1 will cook 4 in 10 min 2 will cook 2 in 6 min 3 will cook 2 in 9 min 4s will cook 1 each in 4 min 4+2+2+1+1 = 10 |
||||||||||||
|
2021-07-14 16:28:18
why tle in python? does this platform doesn't considers slow languages? |
||||||||||||
|
2021-06-30 08:04:47
Easy peasy lemon squeezzzy !!. Very good question on binary search. |
||||||||||||
|
2021-06-19 07:22:16
accepted in second Go!!! |
||||||||||||
RSS