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

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

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.")

</syntaxhighlight>