Scribd
Upload
44 views1 page

SPOJ Problem - Tutorial: SUBSUMS - Subset Sums

The problem involves finding the number of subsets from a sequence of N integers that have a sum within a specified range [A, B]. The input consists of three integers followed by N numbers, and the output is a single integer representing the count of valid subsets. The solution may require techniques such as binary search and bitmasks due to the potential size of the subsets.

Uploaded by

Anil Yogi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
44 views1 page

SPOJ Problem - Tutorial: SUBSUMS - Subset Sums

The problem involves finding the number of subsets from a sequence of N integers that have a sum within a specified range [A, B]. The input consists of three integers followed by N numbers, and the output is a single integer representing the count of valid subsets. The solution may require techniques such as binary search and bitmasks due to the potential size of the subsets.

Uploaded by

Anil Yogi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

SPOJ

Problem | Tutorial
SUBSUMS - Subset Sums

(binary-search,bitmasks)

Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000),


determine how many subsets of S (including the empty one) have a sum between A and B
(-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.

Input

The first line of standard input contains the three integers N, A, and B. The following N lines
contain S1 through SN, in order.
Output

Print a single integer to standard output representing the number of subsets satisfying the
above property. Note that the answer may overflow a 32-bit integer.

Example

Input:
3 -1 2
1
-2
3

Output:
5

Submit on Spoj ([Link]

See Tutorial ([Link]

You might also like