Fişierul intrare/ieşire:liste.in, liste.outSursăLot Sibiu 2011 - Baraj 2 Juniori
AutorMarius NicoliAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Liste

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

Cerinţă

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 liste.in 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 liste.out se găseşte un singur număr natural reprezentând valoarea cerută.

Restricţii

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

Exemplu

liste.inliste.out
4
2 0 1
1 0
3 1 3 3
1 2
2
7
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
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?