View source for 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'''

==Exemplu:==

;Intrare

:25 3 4 11

;Ieșire

:3 7 11 14 15 18 19 22 23 25

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def solve(n, a, x, y):
    # Creăm o listă pentru a ține evidența numerelor pe care le-am vizitat
    visited = [False] * (n + 1)
    
    # Inițializăm coada cu numărul de start 'a'
    queue = deque([a])
    
    # Marcăm numărul 'a' ca vizitat
    visited[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 + x, current + y]:
            if i <= 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(n + 1) if visited[i]]

# Testăm funcția cu datele de intrare
n, a, x, y = 25, 3, 4, 11
print(*solve(n, a, x, y))

</syntaxhighlight>