0867 - Generare2 cu Coada

Enunțul acestei probleme este identic cu cel al problemei #Generare2 . Vă recomandăm să o rezolvați folosind o structură de date de tip coadă.

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

Exemplul 1:

Intrare

25 3 4 11

Ieșire

Datele de intrare corespund restrictiilor impuse.
3 7 11 14 15 18 19 22 23 25

Exemplul 2:

Intrare

generare2 cu coada

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

from collections import deque


def verificare_restrictii(nr_n, nr_a, nr_x, nr_y):    # functia de verificare a datelor de intrare
    if 1 <= nr_n <= 10000 and 1 <= nr_x <= 10000 and 1 <= nr_y <= 10000 and 0 <= nr_a <= 10000:
        return True
    else:
        return False


def solve(nr_n, nr_a, nr_x, nr_y):
    # Creăm o listă pentru a ține evidența numerelor pe care le-am vizitat
    visited = [False] * (nr_n + 1)

    # Inițializăm coada cu numărul de start 'a'
    queue = deque([nr_a])

    # Marcăm numărul 'a' ca vizitat
    visited[nr_a] = True

    # Parcurgem toate numerele din coadă
    while queue:
        # Scoatem numărul curent din coadă
        current = queue.popleft()

        # Adăugăm 'x' și 'y' la numărul curent și verificăm dacă sunt mai mici sau egale cu 'n' și dacă nu au fost vizitate încă
        for i in [current + nr_x, current + nr_y]:
            if i <= nr_n and not visited[i]:
                # Dacă sunt, le adăugăm în coadă și le marcăm ca vizitate
                queue.append(i)
                visited[i] = True

    # Returnăm toate numerele vizitate
    return [i for i in range(nr_n + 1) if visited[i]]


if __name__ == '__main__':
    try:
        n = int(input("Introduceti numarul n: "))     # citirea numarului n
        a = int(input("Introduceti numarul a: "))     # citirea numarului a
        x = int(input("Introduceti numarul x: "))     # citirea numarului x
        y = int(input("Introduceti numarul y: "))     # citirea numarului y

        if verificare_restrictii(n, a, x, y):             # verificam datele de intrare
            print("Datele de intrare corespund restrictiilor impuse.")
            print(*solve(n, a, x, y))                           # apelam functia de rezolvare
        else:
            print("Datele de intrare nu corespund restrictiilor impuse.")
    # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse.")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse.")