FeedADrake
SRM 844 · 2023-01-19 · by misof
Problem Statement
We have a hungry drake. The drake only eats cake.
The drake's stomach capacity is given as the
We have a collection of cakes we can feed to the drake. Their sizes are the elements of the
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
Return the maximum total size of cakes you can feed to the drake.
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.
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.
4700
{1000, 8000, 2000, 5000, 3000}
0
Returns: 12000
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FeedADrake with a public method int feed(int stomach, vector<int> cakes, int excess) · 113 test cases · 2 s / 256 MB per case