Putovanje
레이팅 미적용의견: 0
\(6^{th}\) round, February \(6^{th}\) 2016
Young Mislav loves spending time in nature and, most of all, he loves spending time in forests. The
fresh air and lovely sounds make the forest his favourite location. Mislav has decided to spend this
afternoon in a forest and, because he’s so practical, he’s also decided to stuffhimself with food. His
belly can contain \(C\) amount of food.
He will have the opportunity to eat various fruits of nature (mushrooms, chestnuts, berries, and so on)
while walking through the forest. All fruits are mutually different given their type and he’d like to eat
as much different fruits as possible, but with the condition that he doesn’t overeat. In other words,
the total weight of the fruits he’s eaten must not be larger than \(C\). Also, when Mislav decides to start
eating, he tries to eat every next fruit if it’s possible to eat it and not overeat. In the case when
he doesn’t have the capacity to eat it, he just moves on.
An array of weights of \(N\) fruits represents the weight and order of fruits that Mislav came across in
the forest. Determine the maximum amount of different fruits that Mislav can eat.
The first line of input contains two integers \(N\) and \(C\) (1 ⩽\(N\) ⩽1 000, 1 ⩽\(C\) ⩽1 000 000) from the
task.
The second line contains \(N\) integers \(w@@RISE_MATH_BLOCK_0@@i\) ⩽1000) that represent the fruits’ weight.
The first and only line of output must contain the maximum possible amount of different fruits that
Mislav can eat.
5 5
3 1 2 1 1
7 5
1 5 4 3 2 1 1
5 10
3 2 5 4 3output
output
4
3
3Clarification of the first example: If Mislav decides to start eating from fruit (3), then he will have eaten
3 different fruits (3, 1, 1). If he starts eating from fruit (1), he will have eaten 4 fruits (1, 2, 1, 1).
평가 및 의견
Putovanje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Putovanje