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

# 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")