Connection Status:
Competition Arena > PyramidSequences

PyramidSequences

SRM 591 · 2013-06-25 · by gojira_tc

SRM 591 · 2013-06-25 · by gojira_tc · Math, Simulation
Class Name: PyramidSequences
Return Type: long
Method Name: distinctPairs
Arg Types: (int, int)
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 given ints 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].

Constraints

  • N will be between 2 and 1,000,000,000, inclusive.
  • M will be between 2 and 1,000,000,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous