3960 - Intersectie Siruri

Cerința

Dându-se mai multe șiruri crescătoare de numere naturale, sfârșitul fiecarui astfel de șir fiind marcat de numărul 0, se cere să se afișeze în ordine strict crescătoare, numerele comune tuturor șirurilor.

Date de intrare

Fișierul de intrare intersectiein.txt conține numere naturale separate printr-un spațiu, care formează șiruri crescătoare, fiecare astfel de șir terminându-se cu numărul 0.

Date de ieșire

Fișierul de ieșire intersectieout.txt va conține în ordine strict crescătoare, numerele comune tuturor șirurilor.

Restricții și precizări

• Fiecare șir conține maxim 100.000 de numere.
• Fiecare număr din șir are valori cuprinse între [1, 2^31 - 1].
• În fișierul intersectiein.txt, pot fi maxim 3.000.000 numere.
• Dacă nu avem niciun număr comun se va afișa mesajul nu exista.

Exemplul 1

intersectiein.txt

1 2 3 7 10 0 1 4 5 7 10 0 2 3 7 10 0 2 3 5 7 9 10 0

intersectieout.txt

Datele introduse corespund restricțiilor impuse.

7 10

Explicație

Toate cele 4 șiruri :

1 2 3 7 10

1 4 5 7 10

2 3 7 10

2 3 5 7 9 10

au numerele 7 și 10 valori comune.

Exemplul 2

intersectiein.txt

1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2147483648 0

intersectieout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 3960 - Intersectie Siruri

def validare(serii_val): # functia de validare a datelor de intrare

   if len(serii_val) > 3000000:
       raise ValueError

   for sir in serii_val:
       if len(sir) > 100000:
           raise ValueError

       for numar_val in sir:
           if numar_val < 1 or numar_val > 2**31 - 1:
               raise ValueError

   fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def intersectie(serii_int): # functia de rezolvare

   intersectie_set = set(serii_int[0])
   for sir in serii_int[1:]:
       intersectie_set &= set(sir)

   if intersectie_set:
       fisier_iesire.write(' '.join(map(str, sorted(intersectie_set))))
   else:
       fisier_iesire.write("nu exista")

if __name__ == '__main__':

   fisier_intrare = open("intersectiein.txt", "r")         # declararea fisierelor
   fisier_iesire = open("intersectieout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       serii_main = []
       sir_curent = []
       for linie in fisier_intrare:
           for numar_str in linie.split():
               numar_main = int(numar_str)
               if numar_main == 0:
                   serii_main.append(sir_curent)
                   sir_curent = []
               else:
                   sir_curent.append(numar_main)

       validare(serii_main)                 # apelul functiei de validare
       intersectie(serii_main)               # apelul functiei de rezolvare

   except ValueError:
       fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>