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

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