problema/liste

Liste

Scrie aici despre problema/liste

== include(page="template/taskheader" task_id="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 <tex> L_1 </tex> şi <tex> L_2 </tex> sunt vecine dacă <tex> L_1 </tex> este imediat deasupra lui <tex> L_2 </tex>, sau dacă <tex> L_2 </tex> este imediat deasupra lui <tex> L_1 </tex>. Oricare două liste vecine <tex> L_1 </tex> şi <tex> L_2 </tex> pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din <tex> L_1 </tex> la care se adaugă toate elementele din <tex> L_2 </tex>. Listele <tex> L_1 </tex> şi <tex> L_2 </tex> vor dispărea şi în locul lor va apărea noua listă.
 
h2. 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.
 
h2. 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: <tex> K \: A_1 \: A_2 \: ... \: A_k </tex>. 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.
 
h2. 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ă.
 
h2. Restricţii
 
* $1 &le; L &le; 100.000$;
* Fiecare listă iniţială are cel mult $10$ de elemente;
* Valorile elementelor listelor sunt numere naturale $&le; 120$
 
 
h2. Exemplu
 
table(example). |_. liste.in |_. liste.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
|

== include(page="template/taskfooter" task_id="liste") ==

public

task: liste