All submissions for this problem are available.
Shrema loves dresses and she has a number of clothes kept in her different wardrobes. Today she has to go for a date with her boyfriend,
so she is searching for a particular type of dress which is stored in one of her wardrobes.
Each wardrobe is of varying capacity and the wardrobes are placed next to one another in a single line .
For searching her favorite dress, Shrema has assigned N number of workers.
She does not want the workers to come in each others way neither does she want the dress to get intermixed with one another
so she has decided to partition the total number of ward-robes among the workers and assign a specific set of ward-robes to each worker.
The set of ward-robes are made in such a way that each worker has atleast 1 wardrobe to search in.
Or in other words we can say Shrema wants to divide the wardrobes into N sections (where N is the number of workers) so that every
wardrobe that the ith worker looks through is earlier in the line than every wardrobe that the jth worker has to look through, for i < j.
Shrema now has decided to partition the wardrobe so as to minimize the maximum number of dresses that a worker would have to look
First line of input contains t : no. of test cases. Then t test cases follows:-
Each test case contain n : Number of wardrobes. Then in the next line :
N numbers separated by space denoting number of dress in a wardrobe.
w : Number of workers.
Maximum number of dresses that a worker will have to look through to find the dress in an optimal partitioning of the wardrobe..
1 <= t <= 1000
2 <= n <= 1000
No of dresses in a wardrobe is not greater than 1000.
1 <= w <= n
Input: 3 9 10 20 30 40 50 60 70 80 90 3 4 50 50 50 50 2 6 1 1 1 1000 1 1 3 Output: 170 100 1000
Example case 1. Suppose there were three workers and nine wardrobes with the following number of dress:
10 20 30 40 50 60 70 80 90
She will divide up the wardrobes into the following sections:
10 20 30 40 50 || 60 70 || 80 90
The worker assigned to the first section would have to look through 150 dresses.
The worker assigned to the second section would have to search through 130 dresses, and the last worker would filter through 170 dresses.
In this partitioning, the maximum number of dresses that a worker looks through is 170,i.e.,no other partitioning has less than 170 dresses.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.