Problem Statement

Given three positive integers $n$, $x$, and $y$, we need to find the maximum size of a set $S$ satisfying:

• $S \subseteq {1, 2, \ldots, n}$
• For any $a \in S$ and $b \in S$, $|a - b| \neq x$ and $|a - b| \neq y$

Output the maximum possible cardinality of $S$.

Constraints: $1 \leq n \leq 10^9$, $1 \leq x, y \leq 22$

Observations

The key insight is that the selection pattern exhibits periodicity. Specifically, if a number $a$ is selected, then $a + x$ and $a + y$ cannot be selected. Conversely, if $a$ is not selected, we would ideally select $a + x$ and $a + y$ (if they exist within range). This mutual relationship creates a cycle with period $x + y$.

Approach 1: Simple Greedy

A natural first approach is a greedy selection: iterate through numbers, select a position $a$ if neither $a - x$ nor $a - y$ has been selected already.

#include <bits/stdc++.h>
using namespace std;

const int MAXD = 55;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> selected(MAXD, 0);
    
    for (int i = 1; i <= x + y; ++i) {
        if (!selected[max(i - x, 0)] && !selected[max(i - y, 0)]) {
            selected[i] = 1;
        }
    }
    
    for (int i = 1; i <= x + y; ++i) {
        selected[i] += selected[i - 1];
    }
    
    int answer = (n / (x + y)) * selected[x + y] + selected[n % (x + y)];
    
    if (x > y) swap(x, y);
    
    vector<int> result(MAXD, -1);
    for (int i = 1; i <= y - x; ++i) {
        for (int j = i; j <= x + y; j += y - x) {
            if (result[j] == 0) {
                result[j] = 1;
                result[j + x] = result[j + y] = result[max(j - x, 0)] = result[max(j - y, 0)] = -1;
            }
        }
    }
    
    result[0] = 0;
    for (int i = 1; i <= x + y; ++i) {
        result[i] = result[i - 1] + (result[i] == 1);
    }
    
    answer = max(answer, (n / (x + y)) * result[x + y] + result[n % (x + y)]);
    cout << answer << '\n';
    
    return 0;
}

Issue: This greedy strategy fails. For instance, with $n = 26$, $x = 21$, $y = 5$, the greedy approach selects 11 numbers, but the maximum is actually 13:

1 3 5 7 9 11 13 15 17 19 21 23 25

Approach 2: BFS-Based Propagation

The idea is to maximize overlap of forbidden positions. We want to select two numbers $a$ and $b$ such that $a + x = b + y$ or $a + y = b + x$, causing their respective forbidden ranges to coincide.

This is equivalent to: if a number is selected, we mark its neighbors at distance $x$ and $y$ as unavailable; if not selected, we prefer to select those neighbors.

#include <bits/stdc++.h>
using namespace std;

const int MAXD = 55;

int gcd_ext(int a, int b) {
    return b == 0 ? a : gcd_ext(b, a % b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> greedy(MAXD, 0);
    
    for (int i = 1; i <= x + y; ++i) {
        if (!greedy[max(i - x, 0)] && !greedy[max(i - y, 0)]) {
            greedy[i] = 1;
        }
    }
    
    for (int i = 1; i <= x + y; ++i) {
        greedy[i] += greedy[i - 1];
    }
    
    int answer = (n / (x + y)) * greedy[x + y] + greedy[n % (x + y)];
    
    if (gcd_ext(x, y) != 1 || x == 1 || y == 1) {
        cout << answer << '\n';
        return 0;
    }
    
    if (x > y) swap(x, y);
    
    vector<int> bfs_state(MAXD, -1);
    queue<int> q;
    
    bfs_state[1] = 0;
    q.push(1);
    
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int w = bfs_state[cur] ^ 1;
        
        if (cur + x <= x + y && bfs_state[cur + x] < w) {
            q.push(cur + x);
            bfs_state[cur + x] = w;
        }
        if (cur + y <= x + y && bfs_state[cur + y] < w) {
            q.push(cur + y);
            bfs_state[cur + y] = w;
        }
        if (cur - x >= 1 && bfs_state[cur - x] < w) {
            q.push(cur - x);
            bfs_state[cur - x] = w;
        }
        if (cur - y >= 1 && bfs_state[cur - y] < w) {
            q.push(cur - y);
            bfs_state[cur - y] = w;
        }
    }
    
    bfs_state[0] = 0;
    for (int i = 1; i <= x + y; ++i) {
        bfs_state[i] = bfs_state[i - 1] + (bfs_state[i] ^ 1);
    }
    
    answer = max(answer, (n / (x + y)) * bfs_state[x + y] + bfs_state[n % (x + y)]);
    cout << answer << '\n';
    
    return 0;
}

Issue: While correct for $n = x + y$, this method fails for other values. For $x = 22$, $y = 17$, the BFS approach yields:

3 4 8 9 12 13 14 17 18 19 22 23 24 27 28 29 32 33 37 38

However, the optimal set is:

1 2 3 6 7 8 11 12 13 16 17 21 22 26 27 31 32 36 37

For $n = 40$, this produces an answer 1 less than optimal.

Approach 3: Hybrid DFS + Greedy (Optimal Solution)

Key observation: Once the first $x$ numbers are determined, the entire period is determined. If we know whether $a$ is selected, then $a + x$ is automatically determined.

We enumerate all possibilities for the first $x$ numbers (2^x combinations), then for positions $x+1$ to $x+y$, we apply greeedy selection:

#include <bits/stdc++.h>
using namespace std;

const int MAXD = 50;


int n, x, y;
int best_answer;
vector<int> pattern(MAXD, 0);
vector<int> current(MAXD, 0);

void search(int idx) {
    if (idx == x + 1) {
        memcpy(current.data(), pattern.data(), sizeof(int) * MAXD);
        
        for (int i = x + 1; i <= x + y; ++i) {
            if (!current[max(i - x, 0)] && !current[max(i - y, 0)]) {
                current[i] = 1;
            }
        }
        
        for (int i = 1; i <= x + y; ++i) {
            current[i] += current[i - 1];
        }
        
        int total = (n / (x + y)) * current[x + y] + current[n % (x + y)];
        best_answer = max(best_answer, total);
        return;
    }
    
    pattern[idx] = 1;
    search(idx + 1);
    pattern[idx] = 0;
    search(idx + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> x >> y;
    
    if (x > y) swap(x, y);
    
    best_answer = 0;
    search(1);
    
    cout << best_answer << '\n';
    
    return 0;
}

Complexity: $O((x + y) \cdot 2^{\min(x, y)})$, which is sufficient given that $x, y \leq 22$.

The algorithm exploits the fact that the first $x$ positions fully determine the pattern within each period. By enumerating only these $x$ (or $\min(x, y)$) positions via DFS, we reduce the state space from $2^{x+y}$ to $2^{\min(x,y)}$. For the remaining positions, greedy selection suffices to produce lexicographically minimal valid configurations within each enumerated pattern.