1154 - Cautare Div Imp
De la Universitas MediaWiki
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
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():
# Verificare pentru n
n = int(input())
if not (1 <= n <= 1000):
print("Valoarea lui n nu respectă restricțiile.")
return
a = list(map(int, input().split()))
# Verificare pentru elementele vectorului a
if any(abs(ai) >= 1000000000 for ai in a):
print("Elementele vectorului a depășesc limita de 1.000.000.000.")
return
m = int(input())
# Verificare pentru m
if not (1 <= m <= 1000):
print("Valoarea lui m nu respectă restricțiile.")
return
b = list(map(int, input().split()))
# Verificare pentru elementele vectorului b
if any(abs(bi) >= 1000000000 for bi in b):
print("Elementele vectorului b depășesc limita de 1.000.000.000.")
return
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()