3760 - Intergalactic

Cerința

Într-o galaxie îndepărtată, există două echipe de exploratori intergalactici care explorează planete pentru a găsi resurse rare. Fiecare explorator deține un cod unic ordonat crescător, iar scopul lor este de a găsi exploratorii comuni între cele două echipe pentru a forma o alianță puternică. Să se determine codurile comune ale exploratorilor din cele două echipe, utilizând căutarea binară pentru eficiență.

Date de intrare

Programul citește de la tastatură două liste de numere întregi ordonate crescător, reprezentând codurile unice ale exploratorilor din cele două echipe intergalactice.

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 codurile comune ale exploratorilor din cele două echipe. Dacă nu există exploratori 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_exploratori_echipa1, numar_exploratori_echipa2 ⩽ 100000

Exemplu 1

Intrare

1001 1002 1003 1004 1005
1003 1004 1005 1006 1007

Iesire

Datele de intrare corespund restricțiilor impuse. [1003, 1004, 1005]

Exemplu 2

Intrare

2001 2002 2003
3001 3002 3003

Iesire

Datele de intrare corespund restricțiilor impuse. []

Rezolvare

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

   try:
       echipa_1 = list(map(int, input("Introduceți codurile unice ale exploratorilor din prima echipă: ").split()))
       echipa_2 = list(map(int, input("Introduceți codurile unice ale exploratorilor din a doua echipă: ").split()))
       return echipa_1, echipa_2
   except ValueError:
       return None, None

def valideaza_date(echipa_1, echipa_2):

   if 1 <= len(echipa_1) <= 100000 and 1 <= len(echipa_2) <= 100000:
       if all(-10**9 <= cod <= 10**9 for cod in echipa_1) and all(-10**9 <= cod <= 10**9 for cod in echipa_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_exploratori(echipa_1, echipa_2):

   rezultat = []
   for cod in echipa_1:
       if cautare_binara(echipa_2, cod):
           rezultat.append(cod)
   return rezultat

def main():

   echipa_1, echipa_2 = citeste_exploratori()
   
   if echipa_1 is None or echipa_2 is None:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   if valideaza_date(echipa_1, echipa_2):
       print("Datele de intrare corespund restricțiilor impuse.")
       rezultat = intersectie_exploratori(echipa_1, echipa_2)
       print(rezultat)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

if __name__ == "__main__":

   main()

</syntaxhighlight>