TopCoder problem "ArithmeticalMean" used in TCHS SRM 43 (Division I Level Three)



Problem Statement

    You are given a int[] elements. If the arithmetic mean of a non-empty subset of elements is between L and H, inclusive, the subset is considered "good". A subset of a int[] is obtained by removing 0 or more elements from the int[]. Return the number of "good" subsets.
 

Definition

    
Class:ArithmeticalMean
Method:howMany
Parameters:int[], int, int
Returns:long
Method signature:long howMany(int[] elements, int L, int H)
(be sure your method is public)
    
 

Constraints

-elements will contain between 1 and 36 elements, inclusive.
-Each element of elements will be between -25000000 and 25000000, inclusive.
-Each element of elements will be distinct.
-L and H will each be between -25000000 and 25000000, inclusive.
-L will not be greater than H.
 

Examples

0)
    
{10,1,3}
2
6
Returns: 4
All possible arithmetic means are: 1, 2, 3, 14/3, 11/2, 13/2, 10.

Four of them (2, 3, 14/2, 11/2) make "good" subsets.
1)
    
{0}
-1
0
Returns: 1
There is just one subset and it's "good".
2)
    
{0}
100
100
Returns: 0
Same one subset but it's not "good".
3)
    
{1,2,3,4,5,6,7,8,9,10}
3
7
Returns: 949

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8221

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10792&pm=8221

Writer:

it4.kp

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Search, Simple Math