Connection Status:
Competition Arena > ModularInequality

ModularInequality

SRM 325 · 2006-11-02 · by Andrew_Lazarev

SRM 325 · 2006-11-02 · by Andrew_Lazarev · Geometry, Math
Class Name: ModularInequality
Return Type: int
Method Name: countSolutions
Arg Types: (vector<int>, int)
Problem Statement

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| &#8804; P

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

Submissions are judged against all 161 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ModularInequality with a public method int countSolutions(vector<int> A, int P) · 161 test cases · 2 s / 256 MB per case

Submitting as anonymous