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 L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 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 listeIN.txt are pe prima linie un număr natural L reprezentând numărul de liste. Fiecare dintre următoarele L linii descriu, în ordine, câte o listă şi au structura: K A[1] A[2] … A[K]. Primul element notat K reprezintă numărul de elemente din listă. În continuare sunt K 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 listeOUT.txt 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

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

Exemplul 1:

listeIN.txt

4
2 0 1
1 0
3 1 3 3
1 2

listeOUT.txt

2

Exemplul 2:

listeIN.txt

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

listeOUT.txt

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>