SlowSequence
TCO20 Europe Qualification · 2020-10-02 · by misof
TCO20 Europe Qualification · 2020-10-02 · by misof · Greedy, Simple Math
Problem Statement
Problem Statement
A slow sequence is a sequence A of N elements with the following properties:
- A[0] = 0
- for each valid i, the values A[i] and A[i+1] differ by exactly 1
Given N and S, construct and return any slow sequence with sum S.
Return an empty
Constraints
- N will be between 1 and 2500, inclusive.
- S will be between -10^9 and 10^9, inclusive.
Examples
0)
4
4
Returns: {0, 1, 2, 1 }
The sequence {0, 1, 2, 1} has all the desired properties: element 0 is 0, we have |0-1| = |1-2| = |2-1| = 1, and its sum is 0+1+2+1 = 4.
1)
8
0
Returns: {0, 1, 0, -1, 0, -1, 0, 1 }
2)
1
4700
Returns: { }
3)
5
-10
Returns: {0, -1, -2, -3, -4 }
4)
1
-2
Returns: { }
Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SlowSequence with a public method vector<int> construct(int N, int S) · 121 test cases · 2 s / 256 MB per case