HELPDONN - Help Donn

no tags 

 

PROBLEM CODE:Enigma Treasure Hunt
KaushikRamDonn went to Enigma and registered for 
Treasure Hunt.Following are the rules for Enigma Treasure hunt ,
Rule 1: Donn has to go from 1st stage to nth stage in a sequential order ( only after completing stage 1 ,he can go to stage 2,then to stage 3). 
and collect treasures in a bag
Rule2: Donn will be given only k bags at the time of registration
Rule3: There are bags capable of holding all possible weights and is infinite in number. Donn is free to choose any bags capable of holding any weight (but all the k bags should be capable of holding the same weight)
Pandian,the organiser will give the bag ,Euler asked.
Rule4: once the game is started ,Donn cant exchange his bag .
Rule5: While going through different stages,if Donn couldnt accomodate the treasure in a bag ,tie the bag and give it to Pandian.(this bag cant be used any more.Then start collecting the treasures in a new bag.
Rule6: The cost of the bag is directly proportional to the weight it can hold ,so try to reduce the cost.
Fortunatley ,Donn knows the weights of the treasure in each stage ,Help Donn Choose his bag (maximum bag size needed) .
Example: 
Consider there are 3 stages(n= 3) in the Hunt.the weight of the treasures in each of these stages (which is known to donn before the hunt starts)
are 1,2 and 3. Donn is  allowed to get 2 bags(k= 2) in this example
n = 3, k= 2
stages = {1,2,3}
Donn could accomplish his target if each of his bag can accomodate 3 kg or 5 kg.
Explanation :
if the wieght of the bag is 3 - Stage1 weight + stage2 weight = 1+2=3 <=3 in one bag ,stage 3 weight= 3<=3  in another bag.thus they fit in the bags
if the wieght of the bag is 5 - Stage1 weight = 1<=5 in one bag,stage2 + stage 3 weight= 2+3 =5 <=5 in another bag.thus they fit in the bags
but consider a bag size of 2 :
1 + 2> 2 so put stage1 treasure alone in 1st bag
2 + 3 >2 so put stage2 treasure alone in 2st bag
now we need one more bag to put in the 3rd treasure.
This is not possible so u cant choose a bag of size 2
bag of size >=3 can be used 
Donn is intelligent and so he wants to pay the minimum cost so Donn will purchase a bag of size 3.Help Donn solve his problem .
Input:
0< T <=100 ,no of test cases 
Each test case contains
0<N<=1000,no of stages and then a space followed by
0<k<=1000, no of bags allowed
the next N lines contains the weights of the treasures in each stage
output:
output a single line containing the minimum size of the bag needed.
Example
Input:
1
3 2
1
2
3
output :

 

PROBLEM CODE:Enigma Treasure Hunt

KaushikRamDonn went to Enigma and registered for 

Treasure Hunt.Following are the rules for Enigma Treasure hunt ,

Rule 1: Donn has to go from 1st stage to nth stage in a sequential order ( only after completing stage 1 ,he can go to stage 2,then to stage 3). 

and collect treasures in a bag

Rule2: Donn will be given only k bags at the time of registration

Rule3: There are bags capable of holding all possible weights and is infinite in number. Donn is free to choose any bags capable of holding any weight (but all the k bags should be capable of holding the same weight)

Pandian,the organiser will give the bag to Donn.

Rule4: once the game is started ,Donn cant exchange his bag .

Rule5: While going through different stages,if Donn couldnt accomodate the treasure in a bag ,he will tie the bag and give it to Pandian.(this bag cant be used any more).Then he starts collecting the treasures in a new bag.

Rule6: The cost of the bag is directly proportional to the weight it can hold ,so try to reduce the cost.

Fortunatley ,Donn knows the weights of the treasure in each stage ,Help Donn Choose his bag.

 

Example: 

 

Consider there are 3 stages(n= 3) in the Hunt.the weight of the treasures in each of these stages (which is known to donn before the hunt starts)

are 1,2 and 3. Donn is  allowed to get 2 bags(k= 2) in this example

 

n = 3, k= 2

stages = {1,2,3}

 

Donn could accomplish his target if each of his bag can accomodate 3 kg or 5 kg.

Explanation :

if the wieght of the bag is 3 - Stage1 weight + stage2 weight = 1+2=3 <=3 in one bag ,stage 3 weight= 3<=3  in another bag.thus they fit in the bags

if the wieght of the bag is 5 - Stage1 weight = 1<=5 in one bag,stage2 + stage 3 weight= 2+3 =5 <=5 in another bag.thus they fit in the bags

but consider a bag size of 2 :

1 + 2> 2 so put stage1 treasure alone in 1st bag

2 + 3 >2 so put stage2 treasure alone in 2st bag

now we need one more bag to put in the 3rd treasure.

This is not possible so u cant choose a bag of size 2

bag of size >=3 can be used 

Donn is intelligent and so he wants to pay the minimum cost so Donn will purchase a bag of size 3.Help Donn solve his problem .

 

Input:

0< T <=100 ,no of test cases 

Each test case contains

0<N<=1000,no of stages and then a space followed by

0<k<=1000, no of bags allowed

the next N lines contains the weights of the treasures in each stage
the weight of the treasure <= 1000 . 

output:

output a single line containing the minimum size of the bag needed.

 

 

 

Example

Input:

1

3 2

1

2

3

output :

 

 

 


hide comments
vengatesh15: 2017-02-06 08:56:05

simple binary search Note: need not to use all k bags.

hodobox: 2016-06-15 06:38:12

Not sure what 'tricky cases' can be for this question... but here goes
3
2 1
17
13
5 10
10
40
20
30
20
3 2
1
2
4
ans: 30, 40, 4.

Krishna Nakkeeran: 2014-03-20 16:18:56

some tricky cases please....

Aravindan Chandrasekaran: 2014-03-10 13:01:30

Helped Donn in my 6th Attempt :) :P

Miguel Oliveira: 2013-09-17 10:13:30

Eddy, I used 32 bit signed integers

Eddy R. Morales Perez: 2013-09-17 10:13:30

What is the constraints for the weight of treasure in each stage?


Added by:B.R.ARVIND
Date:2013-09-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET