A deep-space agency is packing sample-return probes for a series of launches. There are n candidate payload modules available, each with a fixed mass. Before every launch, mission control sets a maximum total mass the probe is allowed to carry on that trip. The probe may select any subset of the available modules — order does not matter, and the same module cannot be counted twice in one selection — and mission control wants to know, for each launch's mass allowance, the greatest possible number of modules whose masses sum to no more than that allowance.
Line 1: an integer n, the number of payload modules. Line 2: n space-separated integers mass_1 ... mass_n, the mass of each module. Line 3: an integer q, the number of launches (mass allowances) to evaluate. Line 4: q space-separated integers allowance_1 ... allowance_q.
Print a single line containing q space-separated integers — for each allowance in the order given, the maximum number of modules that can be selected so that their total mass does not exceed that allowance.
Example 1
Input
4 4 5 2 1 2 3 10
Expected
2 3
Explanation
Sorting the module masses ascending gives [1, 2, 4, 5] with running totals 1, 3, 7, 12. For an allowance of 3, the two lightest modules (masses 1 and 2) sum to exactly 3, so at most 2 modules fit. For an allowance of 10, the three lightest modules (1, 2, 4) sum to 7 <= 10, but adding the fourth (mass 5) would bring the total to 12 > 10, so the answer is 3.
Example 2
Input
1 2 1 1
Expected
0
Explanation
There is only one module, with mass 2, and the allowance is 1. Since 2 > 1, the probe cannot afford to carry even that single module, so the maximum count is 0.
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 →