2627 - H1
Enunt[edit | edit source]
Se dau două șiruri de numere naturale a[1], a[2], …, a[n] și b[1], b[2], …, b[m].
Cerinta[edit | edit source]
Să se determine câte numere distincte au în comun cele două șiruri. De exemplu, șirurile a=(2,5,1,4,5,1) și b=(1,1,1,3,7,5) au în comun două numere distincte: 1 și 5.
Date de intrare[edit | edit source]
Programul citește de la tastatură numere naturale A, B, C, D, n, x, m, y. Cele două șiruri se generează astfel:
- a[1] = x și, pentru i ≥ 2, a[i] = A + (a[i-1] * C + D) % (B - A + 1)
- b[1] = y și, pentru i ≥ 2, b[i] = A + (b[i-1] * C + D) % (B - A + 1)
Date de iesire[edit | edit source]
Programul va afișa pe ecran numărul C, reprezentând câte numere distincte au în comun cele două șiruri.
Restrictii si precizari[edit | edit source]
- 2 ⩽ n, m ⩽ 2 000 000
- 2 ⩽ A, B, C, D, x, y ⩽ 10 000 000
Exemplul 1[edit | edit source]
- Intrare
- 1 30 17 16 50 2 60 14
- Iesire
- Datele introduse corespund restrictiilor impuse
- 4
Exemplul 2[edit | edit source]
- Intrare
- 6.2 8 -11 2.2 0 -2.2 8 10
- Iesire
- Datele introduse nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1"> def generate_sequence(A, B, C, D, x, n):
sequence = [x] for i in range(2, n + 1): next_element = (A + (sequence[i - 1] * C + D)) % (B - A + 1) sequence.append(next_element) return sequence
def verificare_date_intrare(A, B, C, D, x, n, m, y):
if not (2 <= n <= 2000000) or not (2 <= m <= 2000000): return False if not (2 <= A <= 10000000) or not (2 <= B <= 10000000) or not (2 <= C <= 10000000) or not (2 <= D <= 10000000): return False if not (2 <= x <= 10000000) or not (2 <= y <= 10000000): return False return True
- Citire date de intrare
A, B, C, D, n, x, m, y = map(int, input().split())
- Verificare date de intrare
if not verificare_date_intrare(A, B, C, D, x, n, m, y):
print("Datele introduse nu corespund restricțiilor impuse")
else:
# Generare șiruri sequence_a = generate_sequence(A, B, C, D, x, n) sequence_b = generate_sequence(A, B, C, D, y, m)
# Identificare numere comune set_a = set(sequence_a) set_b = set(sequence_b) common_numbers = set_a.intersection(set_b)
# Afișare rezultat print(len(common_numbers))
</syntaxhighlight>