| 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
|
||||||||||||
|
2023-12-25 07:35:29
Solution : 1.dry run test case on notebook and see how we get answer 2.make a bool fxn which shows can "time" give us parathas>=P 3.calculate min and max time possible take hints from solution(sum of n terms of ap). 4.iterate time(search space) by Linear search 1st then optimize it by Binary Search . Try to come up with the code by yourself. Here is the Code: <snip> [Simes]: no thanks Last edit: 2023-12-27 09:48:11 |
||||||||||||
|
2023-12-23 16:30:54
What is faster. Heap approach or binary search? |
||||||||||||
|
2023-07-15 08:45:23
guys my solution works for the example test cases given above. But somehow after/at test 2, it gives a wrong answer. I'm not able to get the problem :( |
||||||||||||
|
2023-07-13 06:41:01
I solved it using min_heap <snip> [Simes]: No thanks, this is a site for people who want to write their own code Last edit: 2023-07-13 09:06:44 |
||||||||||||
|
2023-07-09 13:44:45
I used double BS.. wbu guys? |
||||||||||||
|
2023-07-07 14:16:05
<snip> [Simes]: read the footer, don't post code here. Last edit: 2023-07-07 16:42:58 |
||||||||||||
|
2023-05-26 16:10:06
<snip> Last edit: 2023-05-26 16:39:39 |
||||||||||||
|
2023-02-22 09:53:20
Took 2hrs but finally solved! |
||||||||||||
|
2022-06-28 20:01:11
Done in 1st go. Nice and Conceptual Problem. Hint 1 : understand the problem correctly Hint 2 : estimate the largest time required correctly |
||||||||||||
|
2022-03-15 20:55:00
Hint 1: sum of 1st n natural number is n*(n + 1) / 2 Hint 2(in case of TLE in binary Search): high = maximum time to get p paratas not INT_MAX |
||||||||||||
RSS