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

Правка en3, от sensibilityness, 2019-10-25 18:15:36

Edit: The constraints weren't included in the original problem statement! My coach and I failed to solve this problem. I have two RAR archives of test cases for you to judge the validity of your solution. Any suggestions are welcome.

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

Edit (to address this comment): This output is valid as well:

2
40 60
Теги #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский sensibilityness 2019-10-25 19:16:35 2 Tiny change: '_i, l, r \leq 10^{15}' -> '_i, l, r \geq 10^{15}'
en5 Английский 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 Английский sensibilityness 2019-10-25 18:40:03 285 I am feeling really happy.
en3 Английский 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 Английский sensibilityness 2019-10-25 17:40:23 241
en1 Английский sensibilityness 2019-10-25 16:36:08 743 Initial revision (published)