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]]

1. Testăm funcția cu datele de intrare

n, a, x, y = 25, 3, 4, 11 print(*solve(n, a, x, y))

</syntaxhighlight>