2627 - H1: Difference between revisions

Latest revision as of 12:27, 29 December 2023

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>

@@ Line 1: / Line 1: @@
 == Enunt ==
-Se dau două șiruri de numere naturale a[1], a[2], …, a[n] și b[1], b[2], …, b[m].
+Se dau două șiruri de numere naturale '''a[1], a[2], …, a[n]''' și '''b[1], b[2], …, b[m]'''.
 == Cerinta ==
-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.
+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 ==
-Programul citește de la tastatură numere naturale A, B, C, D, n, x, m, y. Cele două șiruri se generează astfel:
+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)
@@ Line 16: / Line 16: @@
 == Date de iesire ==
-Programul va afișa pe ecran numărul C, reprezentând câte numere distincte au în comun cele două șiruri.
+Programul va afișa pe ecran numărul '''C''', reprezentând câte numere distincte au în comun cele două șiruri.
 == Restrictii si precizari ==
-*2 ≤ n, m ≤ 2 000 000
+*2 &les; n, m &les; 2 000 000
-*2 ≤ A, B, C, D, x, y ≤ 10 000 000
+*2 &les; A, B, C, D, x, y &les; 10 000 000
 == Exemplul 1 ==
@@ Line 27: / Line 27: @@
 :1 30 17 16 50 2 60 14
 ;Iesire
-;Datele introduse corespund restrictiilor impuse
+:Datele introduse corespund restrictiilor impuse
 :4
@@ Line 34: / Line 34: @@
 :6.2 8 -11 2.2  0 -2.2 8 10
 ;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def generare_sir(A, B, C, D, x, n):
+def generate_sequence(A, B, C, D, x, n):
-     sir = [x]
+     sequence = [x]
      for i in range(2, n + 1):
-         urmatorul_numar = (A + (sir[i - 1] * C + D)) % (B - A + 1)
+         next_element = (A + (sequence[i - 1] * C + D)) % (B - A + 1)
-         sir.append(urmatorul_numar)
+         sequence.append(next_element)
-     return set(sir)
+     return sequence
-def main():
+def verificare_date_intrare(A, B, C, D, x, n, m, y):
-     # Citirea datelor de intrare
+     if not (2 <= n <= 2000000) or not (2 <= m <= 2000000):
-    A = int(input("Introduceti A: "))
+        return False
-     B = int(input("Introduceti B: "))
+     if not (2 <= A <= 10000000) or not (2 <= B <= 10000000) or not (2 <= C <= 10000000) or not (2 <= D <= 10000000):
-    C = int(input("Introduceti C: "))
+        return False
-    D = int(input("Introduceti D: "))
+     if not (2 <= x <= 10000000) or not (2 <= y <= 10000000):
-     n = int(input("Introduceti n: "))
+        return False
-    x = int(input("Introduceti x: "))
+     return True
-    m = int(input("Introduceti m: "))
-     y = int(input("Introduceti y: "))
-    # Generarea celor două șiruri
+# Citire date de intrare
-    sir_a = generare_sir(A, B, C, D, x, n)
+A, B, C, D, n, x, m, y = map(int, input().split())
-    sir_b = generare_sir(A, B, C, D, y, m)
-     # Calculul intersecției și afișarea rezultatului
+# Verificare date de intrare
-     numere_comune_distincte = len(sir_a.intersection(sir_b))
+if not verificare_date_intrare(A, B, C, D, x, n, m, y):
-     print(f"Numarul de numere distincte comune este: {numere_comune_distincte}")
+    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))
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>