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

hide comments
square1001: 2016-07-26 06:57:55

Yeah, today I've solved 3 meet-in-the-middle algorithm problems.
I love meet-in-the-middle algorithm!
Do you like meet-in-the-middle algorithm?

rajeshranjan: 2016-02-07 09:26:01

great question,good concept building of #bitmask and binary search combo...

manas0008: 2016-02-06 19:16:31

Try to use divide and conquer approach(minimises time & space).....learnt bitmasking.......STL helped a lot!!............It has made my day.

Last edit: 2016-02-06 19:20:40
abhi_6991: 2016-02-06 12:30:56

Bitmasking ,binary search!!!

Last edit: 2016-02-06 13:21:37
minhthai: 2016-01-25 11:09:41

very nice question :D

GAURAV CHANDEL: 2015-12-29 19:25:26

Cool ... very cool....

aghori_sadhu: 2015-10-20 20:22:33

A great question....indeed bitmask + binary search :D

karan: 2015-06-19 16:04:53

nice problem :)

Aman: 2015-05-29 19:27:43

Last edit: 2015-05-29 19:29:11
i_am_looser: 2015-05-24 16:58:18

Finally AC.............. ; )


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