Hi codeforces.
My coach gave me a problem the other day and I'm still stuck in it and I have no idea on how to solve it.
I was wondering if you could help me.
It goes like this:
You are in a candy workshop you have N candies , M boxes with the capacity of C units and each candy has it's own wight.
The candies are in a production line so you can't rearrange them you are standing in the front of the line and you have to bag as many candies as you can.
When a candy piece arrives to you , you have 3 choices
1) take the candy and subtract it's wight from the remaining wight of the box ( as long as it's wight is less or equal to the box's remaining wight)
2) discard the candy( NOTE : that you can not take the candy again )
3) close the box you have and open a new one ( if you have a box left )
What is the maximum number of candies you can bag in the boxes.
NOTE : that you stand in the left of the production line.
1 <= N <= 100000 1 <= M,C <= 100
e.g:
N = 8
M = 2
C = 20
The candies are 12 8 5 10 13 15 4 7
The output is : 5
You can take 12 and 8 and put them in the first box and close it then you can take 5 and 10 and 4 and you're done.
e.g2:
N = 24
M = 1
C = 20
The candies are 13 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 13
The output is : 20