All submissions for this problem are available.
Professor X has to schedule some jobs on a grid of processors. Assume that the execution time of each job scales linearly with the power of the processor. This means, if a particular job takes 2 seconds to finish on a processor with power P, it will take 1 second to finish on a processor with power 2P. He knows the processing power of each processor. Given an array A, containing the execution times of each job on a processor with 1 unit processing power, and the processing powers of the available processor, find the minimum total time taken to complete the concurrent execution of all the jobs (Note: The jobs need not be processed in the given order).
1.The first input will be T, the tumber of testcases. T <= 100
2.The next line will be the number of jobs, N. N <= 10
3.N lines follow. On the ith line, the input is an integer which lies between 1 and 30 inclusive. The ith integer is the time taken to execute the ith job on a processor with a processing power of 1 unit.
4.The next line will contain an integer P, 1 <= P <= 5. P denotes the number of processors.
5.K lines follow. The kth integer is the processing power of the kth processor.
For each test case, output a number which represents the sum of the first 'n' natural numbers.
Input: 2 3 10 1 1 2 20 8 2 4 4 1 7
Output: 0.500000 1.142857
Explanation For the first case, we can use the processor with power 20 to handle the job which takes 10
units of time, and the other processor to handle the left two jobs. The second processor
will be done in 0.25 time units, but the other processor would be half done, and would
finally complete its job after taking 0.5 time units. In the second case, there is only
one processor, and hence the total time taken would be (4+4)/7 = 1.42857 time units.
|Time Limit:||0.421053 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.