A trail crew is packing for a multi-day expedition and already has n ration packs, where the i-th pack supplies exactly nums[i] calories. Before departure they can special-order any number of additional ration packs from the outfitter; each special-order pack may be filled with any calorie amount they choose, from 1 up to a maximum pack size of limit (inclusive), and every order can pick a different amount.
The crew wants full flexibility on the trail: for every whole calorie target from 1 up to a required amount goal, they must be able to select some subset of packs (existing plus special-ordered) whose calories add up to exactly that target. Determine the minimum number of special-order packs the crew needs to place.
The first line contains a single integer n — the number of existing ration packs. The second line contains n space-separated integers nums_1, ..., nums_n — the calorie count of each existing pack. The third line contains two integers limit and goal.
Print a single integer: the minimum number of special-order packs needed so every calorie target from 1 to goal is achievable as a subset sum of the existing packs together with the special-ordered ones.
Example 1
Input
2 1 3 6 10
Expected
2
Explanation
Sorted packs: [1,3]. Starting from nothing, the 1-calorie pack alone lets the crew hit target 0 or 1 (reach becomes 2). The next pack is 3 calories, but with reach only 2 there is a gap at target 2, so the crew must special-order a pack of size min(limit=6, reach=2)=2 first (1 pack ordered so far); that pushes reach to 4, after which the 3-calorie pack extends reach to 7. A gap remains before goal=10, so the crew orders one more pack of size min(6, 7)=6, pushing reach to 13, which now exceeds goal=10. Total special orders: 2.
Example 2
Input
3 1 4 10 5 9
Expected
2
Explanation
Sorted packs: [1,4,10]. The 1-calorie pack alone gives reach 2 (targets 0-1). The next pack is 4 calories, leaving a gap at targets 2-3 since reach is only 2, so the crew orders a pack of size min(limit=5, reach=2)=2 (1 order), lifting reach to 4; the 4-calorie pack then extends reach to 8, covering targets 0-7. The final pack is 10 calories, but reach is only 8, leaving a gap at targets 8-9, so the crew orders a pack of size min(5, 8)=5 (2nd order), lifting reach to 13 — already past goal=9, so the 10-calorie pack is never needed. Total special orders: 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →