0867 - Generare2 cu Coada
De la Universitas MediaWiki
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.")