StablePairsDiv1 | Topcoder Archive

Problem Statement

Consider the set of integers between 1 and n, inclusive, and two positive integers c and k. You want to build an ordered list of k pairs (x₁, y₁), (x₂, y₂), ... (x_k, y_k) such that the following conditions are met.

1 ≤ x_i < y_i ≤ n for all i between 1 and k, inclusive.
y_i < x_i+1 for all i between 1 and k-1, inclusive.
(x_i+1 + y_i+1) - (x_i + y_i) = c for all i between 1 and k-1, inclusive.

If a list of pairs satisfies all of the above conditions, the list is said to be stable. For any fixed n, c, and k, a stable list of k pairs is said to be maximal if its sum of elements (the sum of all 2k integers it contains) is the largest among all stable lists of k pairs.

For instance, consider n=5, c=4, and k=2. There are two stable lists of pairs: one is [(1, 2), (3, 4)] and the other is [(2, 3), (4, 5)]. The latter is the only maximal stable list of pairs in this example as its sum is (2+3+4+5) = 14.

Given n, c, and k, find one maximal stable list of pairs, and return a int[] that describes the list. Specifically, if (x₁, y₁), (x₂, y₂), ..., (x_k, y_k) is your maximal stable list of pairs, you must return { x₁, y₁, x₂, y₂, ..., x_k, y_k }.

If there are many maximal stable lists of pairs, you may return any one of them. If no stable list of pairs with the desired properties exists, you must return an empty int[].

Definition

Class:: StablePairsDiv1
Method:: findMaxStablePairs
Parameters:: int, int, int
Returns:: int[]
Method signature:: int[] findMaxStablePairs(int n, int c, int k)
(be sure your method is public)

Constraints

n will be between 1 and 100, inclusive.
c will be between 1 and 100, inclusive.
k will be between 1 and 100, inclusive.

Examples

```
5
```
```
4
```
```
2
```
```
Returns: {2, 3, 4, 5 }
```
This example was described in the problem statement.
```
4
```
```
4
```
```
2
```
```
Returns: {1, 2, 3, 4 }
```
```
1
```
```
100
```
```
1
```
```
Returns: { }
```
When n=1, regardless of c and k, there is no way to build a pair.
```
3
```
```
100
```
```
1
```
```
Returns: {2, 3 }
```
With k=1 we are looking for stable lists that only contain a single pair of numbers. There are three stable lists: [(1, 2)], [(1, 3)], and [(2, 3)]. Obviously, the last one is the only maximal one in this case.
```
10
```
```
6
```
```
3
```
```
Returns: {2, 5, 6, 7, 9, 10 }
```
```
12
```
```
7
```
```
3
```
```
Returns: {4, 5, 6, 10, 11, 12 }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.