3648 - Pitici

Cerința

Într-un tărâm îndepărtat, există două grupuri de pitici care se pregătesc să își unească forțele pentru a găsi comori ascunse. Fiecare pitic poartă un număr magic pe pălăria sa, iar aceste numere sunt ordonate crescător în ambele grupuri. Să se determine care sunt piticii comuni în cele două grupuri, utilizând căutarea binară pentru a face operațiunea cât mai eficientă.

Date de intrare

Programul citește de la tastatură două liste de numere întregi ordonați crescător, reprezentând numerele magice purtate de piticii din cele două grupuri.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În următorul rând se va afișa pe ecran lista cu numerele magice comune celor două grupuri de pitici. Dacă nu există pitici comuni, se va afișa o listă goală.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ⩽ numar_pitici_grup1, numar_pitici_grup2 ⩽ 100000

Exemplu 1

Intrare

1 2 3 4 5
3 4 5 6 7

Iesire

Datele de intrare corespund restricțiilor impuse. [3, 4, 5]

Rezolvare

<syntaxhighlight lang="python" line> def citeste_pitici():

   try:
       grup_1 = list(map(int, input("Introduceți numerele magice ale primului grup de pitici: ").split()))
       grup_2 = list(map(int, input("Introduceți numerele magice ale celui de-al doilea grup de pitici: ").split()))
       return grup_1, grup_2
   except ValueError:
       return None, None

def valideaza_date(grup_1, grup_2):

   if 1 <= len(grup_1) <= 100000 and 1 <= len(grup_2) <= 100000:
       if all(-10**9 <= numar <= 10**9 for numar in grup_1) and all(-10**9 <= numar <= 10**9 for numar in grup_2):
           return True
   return False

def cautare_binara(lista, element):

   stanga, dreapta = 0, len(lista) - 1
   while stanga <= dreapta:
       mijloc = (stanga + dreapta) // 2
       if lista[mijloc] == element:
           return True
       elif lista[mijloc] < element:
           stanga = mijloc + 1
       else:
           dreapta = mijloc - 1
   return False

def intersectie_pitici(grup_1, grup_2):

   rezultat = []
   for numar in grup_1:
       if cautare_binara(grup_2, numar):
           rezultat.append(numar)
   return rezultat

def main():

   grup_1, grup_2 = citeste_pitici()
   
   if grup_1 is None or grup_2 is None:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   if valideaza_date(grup_1, grup_2):
       print("Datele de intrare corespund restricțiilor impuse.")
       rezultat = intersectie_pitici(grup_1, grup_2)
       print(rezultat)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

if __name__ == "__main__":

   main()

</syntaxhighlight>