508 - Cautare Binara
Cerinţa
Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. 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 şi precizări
- 1 ⩽ n ⩽ 25.000
- 1 ⩽ m ⩽ 200.000
- elementele celor 2 vectori vor fi mai mici decât 1.000.000.000
Exemplul 1
- Intrare
7 1 2 5 6 9 10 14 8 8 14 9 14 16 15 4 2
- Iesire
0 1 1 1 0 0 0 1
Exemplul 2
- Intrare
30000 1 2 5 6 9 10 14 8 8 14 9 14 16 15 4 2
- Iesire
Datele de intrare nu corespund restrictiilor impuse
Rezolvare
<syntaxhighlight lang="python" line> def verifica_elemente():
n_val = int(input("Introduceti numarul n: "))
x_val = list(map(int, input("Introduceti elementele vectorului x: ").split()))
m_val = int(input("Introduceti numarul m: "))
y_val = list(map(int, input("Introduceti elementele vectorului y: ").split()))
if not (1 <= n_val <= 25000) or not (1 <= m_val <= 200000):
return "Datele de intrare nu corespund restrictiilor impuse"
if max(x_val) >= 1000000000 or max(y_val) >= 1000000000:
return "Datele de intrare nu corespund restrictiilor impuse"
x_set = set(x_val)
rezultat = [1 if elem in x_set else 0 for elem in y_val]
return " ".join(map(str, rezultat))
print(verifica_elemente())
</syntaxhighlight>