Vizualizare sursă pentru „0687 - liste”

== Enunt == 

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste <code>L1</code> şi <code>L2</code> sunt vecine dacă <code>L1</code> este imediat deasupra lui <code>L2</code>, sau dacă <code>L2</code> este imediat deasupra lui <code>L1</code>. Oricare două liste vecine <code>L1</code> şi <code>L2</code> pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din <code>L1</code> la care se adaugă toate elementele din <code>L2</code>. Listele <code>L1</code> şi <code>L2</code> vor dispărea şi în locul lor va apărea noua listă.

= Cerința =
Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

= Date de intrare =
Fişierul <code>listeIN.txt</code> are pe prima linie un număr natural <code>L</code> reprezentând numărul de liste. Fiecare dintre următoarele <code>L</code> linii descriu, în ordine, câte o listă şi au structura: <code>K A[1] A[2] … A[K]</code>. Primul element notat <code>K</code> reprezintă numărul de elemente din listă. În continuare sunt <code>K</code> numere naturale care reprezintă elementele listei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

= Date de ieșire =
Pe prima linie a fişierului <code>listeOUT.txt</code> se găseşte un singur număr natural reprezentând valoarea cerută. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ L ≤ 100.000</code>
* fiecare listă iniţială are cel mult <code>10</code> de elemente;
* valorile elementelor listelor sunt numere naturale <code>≤ 120</code>

= Exemplul 1: =
<code>listeIN.txt</code>
 4
 2 0 1
 1 0
 3 1 3 3
 1 2
<code>listeOUT.txt</code>
 2

= Exemplul 2: =
<code>listeIN.txt</code>
 100001
 3 1 11 111 
 3 2 22 112
 3 2 11 113
 3 1 22 6
 3 5 55 9
 3 7 77 9
 3 8 88 6
<code>listeOUT.txt</code>
 Datele nu corespund restrictiilor impuse

= Explicație =
Avem patru liste. Putem unifica prima și a doua listă, acestea fiind înlocuite cu o singură lista. Apoi putem unifica lista rezultată la primul pas cu lista care iniţial era a treia. Obţinem astfel două liste care nu mai pot fi unificate.
:

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def unifica_liste(liste):
    a_avut_loc_unificare = True
    while a_avut_loc_unificare:
        a_avut_loc_unificare = False
        liste_noi = []
        i = 0
        while i < len(liste):
            if i < len(liste) - 1 and liste[i].intersection(liste[i + 1]):
                lista_unificata = liste[i].union(liste[i + 1])
                liste_noi.append(lista_unificata)
                i += 2
                a_avut_loc_unificare = True
            else:
                liste_noi.append(liste[i])
                i += 1
        liste = liste_noi
    return len(liste)

def citeste_date_intrare(nume_fisier_intrare):
    liste = []
    try:
        with open(nume_fisier_intrare, 'r') as f:
            n = int(f.readline().strip())
            for _ in range(n):
                linie = f.readline().strip().split()
                k, numere = int(linie[0]), list(map(int, linie[1:]))
                liste.append(set(numere))
    except:
        # Dacă apare orice eroare, returnăm None pentru a indica o problemă
        return None
    return liste

def verifica_restricii(liste):
    if not 1 <= len(liste) <= 100000:
        return False
    for lista in liste:
        if not 1 <= len(lista) <= 10 or any(x < 0 or x > 120 for x in lista):
            return False
    return True

def scrie_date_iesire(nume_fisier_iesire, mesaj):
    with open(nume_fisier_iesire, 'w') as f:
        f.write(mesaj + '\n')

def main():
    nume_fisier_intrare = "listeIN.txt"
    nume_fisier_iesire = "listeOUT.txt"
    liste = citeste_date_intrare(nume_fisier_intrare)
    
    if liste is None or not verifica_restricii(liste):
        # Dacă datele sunt invalide sau nu respectă restricțiile, scriem mesajul de eroare
        scrie_date_iesire(nume_fisier_iesire, "Datele nu corespund restrictiilor impuse")
    else:
        numar_liste_finale = unifica_liste(liste)
        scrie_date_iesire(nume_fisier_iesire, str(numar_liste_finale))

if __name__ == "__main__":
    main()
</syntaxhighlight>