FeedADrake | Topcoder Archive

Problem Statement

We have a hungry drake. The drake only eats cake.

The drake's stomach capacity is given as the int stomach. Its stomach is currently empty.

We have a collection of cakes we can feed to the drake. Their sizes are the elements of the int[] cakes.

As long as the drake feels hungry, we can select one of the cakes and feed it to the drake. Once the drake is fed a cake, it will eat the whole cake, even if doing so exceeds its stomach capacity - it will somehow stuff all of the cake into its digestive tract.

When does the drake stop feeling hungry? This is determined by the int excess. If excess = 0, the drake stops feeling hungry as soon as the total amount of cake eaten reaches or exceeds its stomach capacity. If excess is positive, the drake stops feeling hungry only after eating excess additional cakes.

Return the maximum total size of cakes you can feed to the drake.

Definition

Class:: FeedADrake
Method:: feed
Parameters:: int, int[], int
Returns:: int
Method signature:: int feed(int stomach, int[] cakes, int excess)
(be sure your method is public)

Constraints

stomach will be between 1 and 10,000, inclusive.
cakes will have between 1 and 100 elements, inclusive.
All elements of cakes will be positive.
The sum of cakes will not exceed 10^9.
excess will be between 0 and 100, inclusive.

Examples

```
1234
```
```
{10, 20, 30, 40}
```
```
0
```
```
Returns: 100
```
The drake will eat all four cakes. Its stomach capacity hasn't been reached yet, but we are already out of cake.
```
100
```
```
{100, 100, 100}
```
```
0
```
```
Returns: 100
```
Any one of these three cakes is exactly enough to fill the drake's stomach. Once the drake is full, it won't eat any other cakes.
```
101
```
```
{100, 100, 100}
```
```
0
```
```
Returns: 200
```
Now the drake is still a bit hungry after the first cake so you can then stuff a whole second cake down its throat.
```
101
```
```
{100, 100, 100, 100, 100}
```
```
2
```
```
Returns: 400
```
The drake's stomach becomes full while it eats the second cake. But as excess=2, its body does not realize this yet. We can stuff two more cakes into its mouth before the drake realizes that it's full.

{1000, 8000, 2000, 5000, 3000}

Returns: 12000

{100001, 100002, 100003}

Returns: 200005

```
100
```
```
{1000, 2000}
```
```
7
```
```
Returns: 3000
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.