SUBSUMS - Subset Sums

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

The following 5 subsets have a sum between -1 and 2:

  • 0 = 0 (the empty subset)
  • 1 = 1
  • 1 + (-2) = -1
  • -2 + 3 = 1
  • 1 + (-2) + 3 = 2

Added by:Neal Wu
Date:2009-01-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO

hide comments
2014-03-26 18:44:17 innovolt
start from brute force and then small optimization,not too tough as it seems...
2014-02-15 20:19:28 paras meena
I think weak Test cases =P
2014-02-05 22:20:23 Rishav Goyal
really enjoyed !! while solving it !!
2014-01-24 19:03:47 aqfaridi
nice..
2013-08-29 20:37:39 Sumit Kumar
Can the numbers in the sequence repeat?
2013-08-20 17:14:32 super human
awesome problem....learnt something new..!!!
2013-03-16 22:36:27 Tejas Joshi
Really nice problem !!
2009-08-31 08:59:15 :D
There are 2^N subsets for a given set and ALL are counted as distinct.
2009-08-30 11:22:46 pankaj
what should do if there is an element in set value "0".
1.if empty set and {0} are same?
2.if s={1,-2,0} then {1,0}and {1}are different set?
3.if two or more elements can be same of every element will different?

Last edit: 2009-08-30 11:24:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.