1154 - Cautare Div Imp: Difference between revisions

Revision as of 14:37, 2 January 2024

Cerința

Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, verificați pentru fiecare element al vectorului y dacă apare în x.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.

Date de ieșire

Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv 0 în caz contrar.

Restricții si precizări

1 ≤ n,m ≤ 1000
elementele celor doi vectori vor fi mai mici decât 1.000.000.000

Exemplu:

Intrare

7

9 6 5 14 2 1 10

8

8 14 9 14 16 15 4 2

Ieșire

0 1 1 1 0 0 0 1

Rezolvare

<syntaxhighlight lang="python"> def gasesc(elem, a, st, dr):

   if st == dr:
       return a[st - 1] == elem
   else:
       mij = (st + dr) // 2
       return gasesc(elem, a, st, mij) or gasesc(elem, a, mij + 1, dr)

def main():

   n = int(input())
   a = list(map(int, input().split()))
   m = int(input())
   b = list(map(int, input().split()))

   for i in range(1, m + 1):
       if gasesc(b[i - 1], a, 1, n):
           print(1, end=' ')
       else:
           print(0, end=' ')

if __name__ == "__main__":

   main()

</syntaxhighlight>

@@ Line 1: / Line 1: @@
-Cerinta
+== Cerința ==
 Se dă un vector x cu n elemente numere naturale, și un vector y cu m elemente, de asemenea numere naturale. Folosind metoda Divide et Impera, verificați pentru fiecare element al vectorului y dacă apare în x.
-Date de intrare
+== Date de intrare ==
 Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.
-Date de iesire
+== Date de ieșire ==
 Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv 0 în caz contrar.
-Restrictii si precizari
+== Restricții si precizări ==
-≤ n,m ≤ 1000
+* 1 ≤ n,m ≤ 1000
+* elementele celor doi vectori vor fi mai mici decât 1.000.000.000
-elementele celor doi vectori vor fi mai mici decât 1.000.000.000
+=== Exemplu: ===
+'''Intrare'''
-Exemplu
-Intrare
@@ Line 29: / Line 24: @@
 14 9 14 16 15 4 2
-Iesire
+'''Ieșire'''
 1 1 1 0 0 0 1
-''<u>Rezolvare</u>''
+== Rezolvare ==
+<syntaxhighlight lang="python">
-def cautare_divide_et_impera(x, y):
+def gasesc(elem, a, st, dr):
+    if st == dr:
-    rezultat = []
+        return a[st - 1] == elem
+    else:
-    for elem in y:
+        mij = (st + dr) // 2
+        return gasesc(elem, a, st, mij) or gasesc(elem, a, mij + 1, dr)
-        rezultat.append(cauta_element(x, elem))
-    return rezultat
-def cauta_element(x, elem):
-    stanga, dreapta = 0, len(x) - 1
-    while stanga <= dreapta:
-        mijloc = (stanga + dreapta) // 2
-        if x[mijloc] == elem:
-            return 1
-        elif x[mijloc] < elem:
-            stanga = mijloc + 1
-        else:
-            dreapta = mijloc - 1
-    return 0
 def main():
+    n = int(input())
+    a = list(map(int, input().split()))
+    m = int(input())
+    b = list(map(int, input().split()))
-    n = int(input("Introduceți lungimea vectorului x: "))
+    for i in range(1, m + 1):
+        if gasesc(b[i - 1], a, 1, n):
-    x = list(map(int, input("Introduceți elementele vectorului x separate prin spațiu: ").split()))
+            print(1, end=' ')
+        else:
-    m = int(input("Introduceți lungimea vectorului y: "))
+            print(0, end=' ')
-    y = list(map(int, input("Introduceți elementele vectorului y separate prin spațiu: ").split()))
-    rezultat = cautare_divide_et_impera(sorted(x), y)
-    print(*rezultat)
 if __name__ == "__main__":
+    main()
-    main()
+</syntaxhighlight>