Pick elements from an array so that their sum lies within an interval

Revision en1, by sensibilityness, 2019-10-25 16:36:08

Given an array of $$$n$$$ positive integers and an interval $$$[l, r]$$$, you need to pick some elements from this array so that their sum lies within the interval $$$[l, r]$$$.

Input:
The first line contains three positive integers $$$n$$$, $$$l$$$ and $$$r$$$. The second line contains the elements of the array.

Output:
Print one line containing an integer denoting the number of elements chosen and another line containing a space-delimited list of elements sorted in ascending order.

Note: If there are multiple solutions, print any of them.

Sample test case:

Input:

7 80 100
10 20 30 40 50 60 70

Output:

3
20 30 40
Tags #dynamic programing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English sensibilityness 2019-10-25 19:16:35 2 Tiny change: '_i, l, r \leq 10^{15}' -> '_i, l, r \geq 10^{15}'
en5 English sensibilityness 2019-10-25 19:09:24 525 Tiny change: 'ts!** $w_i$s are the e' -> 'ts!** $w_i\text{s}$ are the e'
en4 English sensibilityness 2019-10-25 18:40:03 285 I am feeling really happy.
en3 English sensibilityness 2019-10-25 18:15:36 147 Tiny change: '20 30 40\n' -> '20 30 40\n\nThis output is valid as well:\n\n 2\n 40 60'
en2 English sensibilityness 2019-10-25 17:40:23 241
en1 English sensibilityness 2019-10-25 16:36:08 743 Initial revision (published)