ArithmeticProgression
SRM 413 · 2008-08-05 · by yuhch123
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13... is an arithmetic progression with common difference 2. An arithmetic sequence can always be represented as an=a0+n*d.
You will be given a sequence seq, where seqi = [ai+1] for some nondecreasing arithmetic sequence a (both indices are 0-based). [x] denotes the floor function (see Notes). The sequence a is defined as a0+i*d. Return the minimal possible value for d. If no possible value exists for d, return -1 instead.
Notes
- [x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0, [-1.2] = -2 and [-0.6] = -1.
- Your return value must be accurate to within an absolute or relative tolerance of 1E-9.
Constraints
- seq will contain between 0 and 50 elements, inclusive.
- Each element of seq will be between -10^6 and 10^6, inclusive.
- a0 will be between -10^6 and 10^6, inclusive.
0
{6, 13, 20, 27}
Returns: 6.75
1
{2, 3, 4, 5, 6}
Returns: 1.0
3
{}
Returns: 0.0
Since the sequence a is nondecreasing, d must be at least 0.
3
{3, 3, 3, 3, 4}
Returns: 0.2
1
{-3}
Returns: -1.0
Submissions are judged against all 161 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ArithmeticProgression with a public method double minCommonDifference(int a0, vector<int> seq) · 161 test cases · 2 s / 256 MB per case