1154 - Cautare Div Imp

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>