TopCoder problem "ModularInequality" used in SRM 325 (Division I Level Two , Division II Level Three)



Problem Statement

    

You will be given a int[] A that contains N elements and an int P. Return the number of distinct integer values of X for which the following inequality is true: 

|A0 - X| + |A1 - X| + ... + |AN-1 - X| ≤ P
 

Definition

    
Class:ModularInequality
Method:countSolutions
Parameters:int[], int
Returns:int
Method signature:int countSolutions(int[] A, int P)
(be sure your method is public)
    
 

Constraints

-A will contain between 1 and 50 elements, inclusive.
-Each element of A will be between -1,000,000,000 and 1,000,000,000 inclusive.
-P will be between 0 and 1,000,000,000 inclusive.
 

Examples

0)
    
{1, 2, 3}
6
Returns: 5
The possible values for X are 0, 1, 2, 3 and 4.
1)
    
{10, 30, 15, -1, 17}
42
Returns: 7
2)
    
{0, 2, 3, -5, 10}
17
Returns: 0
3)
    
{-693}
1265
Returns: 2531
4)
    
{965, -938, -396, -142, 926, 31, -720}
6495
Returns: 1781

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10005&pm=6765

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Geometry, Math