PyramidSequences
SRM 591 · 2013-06-25 · by gojira_tc
SRM 591 · 2013-06-25 · by gojira_tc · Math, Simulation
Problem Statement
Problem Statement
A pyramid sequence of height X > 1 is an infinite sequence of positive integers with period 2X-2. Its first 2X-2 terms are 1, 2, ..., X-1, X, X-1, ..., 2.
You are givenint s N and M. Consider two pyramid sequences A and B, A of height N and B of height M. Return the number of distinct pairs of integers (x,y) such that for some i > 0 we have x=A[i] and y=B[i].
You are given
Constraints
- N will be between 2 and 1,000,000,000, inclusive.
- M will be between 2 and 1,000,000,000, inclusive.
Examples
0)
3 4 Returns: 6
These are the first several terms of pyramid sequences of height 3 and 4: {1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1} {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1} We can see the following pairs: (1, 1), (2, 2), (3, 3), (2, 4), (1, 3), (3, 1). No other pairs will appear later in the sequences.
1)
3 5 Returns: 5
The sequences begin with: {1, 2, 3, 2, 1, 2, 3, 2, 1} {1, 2, 3, 4, 5, 4, 3, 2, 1}
2)
43 76 Returns: 895
3)
2 1000000000 Returns: 1000000000
4)
100000 95555 Returns: 4777750000
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PyramidSequences with a public method long long distinctPairs(int N, int M) · 92 test cases · 2 s / 256 MB per case