Question

#867 pbinfo
Cerința
Se dau patru numere naturale n a x y. Să se afișeze elementele mulțimii M, cu următoarele proprietăți:

toate elementele lui M sunt numere naturale mai mici sau egale cu n;
a se află în M;
dacă b se află în M, atunci b+x și b+y se află în M.
Date de intrare
Programul citește de la tastatură numerele n a x y.

Date de ieșire
Programul va afișa pe ecran elementele mulțimii M, în ordine crescătoare, separate prin câte un spațiu.

Restricții și precizări
1 ≤ n ≤ 10000
1 ≤ x , y ≤ 10000
0 ≤ a ≤ 10000



Exemplu
Intrare

25 3 4 11
Ieșire

3 7 11 14 15 18 19 22 23 25

Answer 1

#include <iostream>
#include <queue>
using namespace std;

int v[10001];

int main() {
    int n, a, x, y;
    cin >> n >> a >> x >> y;
    queue <int> c;
    c.push(a);
    v[a] = true;
    while(!c.empty()) {
        int val = c.front();
        if(val + x <= n && !v[val + x])  {
          c.push(val + x);
          v[val + x] = true;
        }
        
        if(val + y <= n && !v[val + y]) {
          c.push(val + y);
          v[val + y] = true;
        }
        c.pop();
    }
    for(int i = 0; i <= n; i++)
      if(v[i] == true)
        cout << i <<" ";
    return 0;
}

Observatie :

Avand in vedere faptul ca vectorul este folosit doar pentru a marca elementele care au fost adaugate in coada, se poate utiliza bitset (daca stii ce este) pentru economisirea memoriei.