Woburn Challenge 2018-19 Round 2 - Junior Division

Problem 4: Ammunition

Ethan Hunt is really in the thick of things now — having infiltrated escaped convict Solomon Lane's hideout in the Rocky Mountains, he's now found himself surrounded by N (1 ≤ N ≤ 1000) of Solomon's guards, with but a single tranquilizer gun to defend himself!

The tranquilizer gun can hold up to M (1 ≤ M ≤ 1000) bullets at a time, and Ethan initially has it loaded with S (0 ≤ S ≤ M) bullets.

Hitting a guard with a single bullet is enough to tranquilize them, and of course, Ethan never misses. The problem is, he might simply not have enough bullets to tranquilize all of the guards. Fortunately, a potential solution has occurred to Ethan — some of the guards appear to be carrying bullets compatible with his gun, which he might be able to grab and use for himself!

The i-th guard is carrying B_i (0 ≤ B_i ≤ 1000) bullets, which they'll drop upon being tranquilized. This means that, if Ethan chooses to use up a bullet to tranquilize the i-th guard, he can then load up to B_i new bullets into his tranquilizer gun immediately afterwards. However, he may only use a number of new bullets which will not cause his gun's new bullet count to exceed M. He also may not leave excess bullets lying around and load them into his gun later on, as they'll get lost amidst the chaotic firefight.

Ethan may tranquilize 0 or more of the N guards in any order he'd like, as long as he always has at least one bullet available in his gun to tranquilize the next guard. What's the maximum number of guards who he can tranquilize?

Subtasks

In test cases worth 16/40 of the points, N ≤ 10 and M = 1000.
In test cases worth another 14/40 of the points, M = 1000.

Input Format

The first line of input consists of three space-separated integers, N, M, and S.
N lines follow, the i-th of which consists of a single integer, B_i, for i = 1..N.

Output Format

Output a single integer, the maximum number of guards who Ethan can tranquilize.

Sample Input 1

3 1000 1
0 1 2

Sample Output 1

3

Sample Input 2

6 2 2
1 0 0 3 0 0

Sample Output 2

5

Sample Explanation

In the first case, Ethan could first choose to tranquilize the 2nd guard, using up his only bullet but then picking up another bullet. He could then use that bullet to tranquilize the 3rd guard, picking up two new bullets as a result. Finally, he could use one of those bullets to tranquilize the 1st guard.

In the second case, Ethan could choose to tranquilize guards 1, 2, 4, 3, and 6, in that order. This would leave him with no bullets remaining to tranquilize the 5th guard, but tranquilizing 5 out of the 6 guards is the best he can do.

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 14, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)