== include(page="template/taskheader" task_id="dictree") ==
Poveste si cerinta...
Pe parcursul acestei probleme, vom numi *litera* oricare dintre cele $52$ de caractere latine (litere mari si mici, care sunt considerate diferite). Numim *arbore dictionar* un arbore cu radacina, care are fiecare muchie etichetata cu o litera. Un cuvant (succesiune finita de litere) poate fi regasit intr-un arbore dictionar daca exista un drum care coboara in arbore, pornind de la radacina, astfel incat muchiile de pe drum sa fie etichetate cu literele care formeazÇŽ cuvantul, in ordine.
*Un exemplu valoreaza cat 1000 de cuvinte.*
!problema/dictree?dictree.jpg!
Acest arbore dictionar are 10 noduri. Urmatoarele cuvinte se pot regasi in acest arbore dictionar: *M*, *MI*, *MIT*, *Ma*, *i*, *io*, *ioi*, *iq*, *C*.
Cateva exemple de cuvinte care nu se pot regasi in acest arbore dictionar: *Pascal*, *a*, *oi*, *MIM*.
Fiind dat un set de cuvinte, exista o infinitate de arbori dictionar in care se regasesc toate aceste cuvinte. Determinati numarul de noduri ale arborelui cu cele mai putine noduri.
h2. Date de intrare
Fisierul de intrare $dictree.in$ ...
Pe prima linie a fisierului de intrare $dictree.in$ este scris numarul $N$ de cuvinte. Pe fiecare din urmatoarele $N$ linii se gaseste cate un cuvant (succesiune de litere fara spatii). Cuvintele nu sunt neaparat distincte.
h2. Date de iesire
In fisierul de iesire $dictree.out$ ...
Fisierul de iesire $dictree.out$ va contine o singura linie, pe care va fi scris numarul minim de noduri ale unui arbore dictionar in care se regasesc cuvintele date.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $0 ≤ N ≤ 25.000$
* $1 ≤ numarul de litere dintr-un cuvant ≤ 100$
h2. Exemplu
table(example). |_. dictree.in |_. dictree.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
| 5
io
iq
C
ioi
MIT
|9|
== include(page="template/taskfooter" task_id="dictree") ==
