Download - Enunt
-
7/23/2019 Enunt
1/2
7/29/2015 Dictree
http://www.infoarena.ro/problema/dictree 1/2
Vezi solutiile trimise | Statistici
Fiierul intrare/ieire: dictree.in, dictree.out Surs Selectie echipe ACM ICPC, UPB 2008
Autor Mihai Patrascu Adugat de Mugurel Ionut Andreica mugurelionut
Timp execuie pe test 0.1 sec Limit de memorie 9000 kbytes
Scorul tu 100 puncte Dificultate N/A
Dictree
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 formeaza cuvantul, in ordine.
Un exemplu valoreaza cat 1000 de cuvinte.
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.
Date de intrare
Pe prima linie a fisierului de intrare dictree.ineste 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.
Date de iesireFisierul 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.
Restrictii0 N 25.000
1 numarul de litere dintrun cuvant 100
Exemplu
dictree.in dictree.out
5
io
iq
C
ioi
9
http://www.infoarena.ro/cauta-probleme?tag_id[]=155http://www.infoarena.ro/implica-te/extinde-arhiva/http://www.infoarena.ro/utilizator/mugurelionuthttp://www.infoarena.ro/utilizator/mugurelionut?action=ratinghttp://www.infoarena.ro/utilizator/mugurelionuthttp://www.infoarena.ro/utilizator/mugurelionut?action=ratinghttp://www.infoarena.ro/utilizator/mugurelionuthttp://www.infoarena.ro/monitor?task=dictreehttp://www.infoarena.ro/cauta-probleme?tag_id[]=155http://www.infoarena.ro/utilizator/mugurelionuthttp://www.infoarena.ro/implica-te/extinde-arhiva/http://www.infoarena.ro/statistici_problema?task=dictree -
7/23/2019 Enunt
2/2
7/29/2015 Dictree
http://www.infoarena.ro/problema/dictree 2/2
2004-2015 Asociatia infoarena
MIT
Vezi solutiile trimise de tine
Cum se trimit solutii?
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
este publicat sub licenta Creative Commons Attribution-NonCommercial 2.5.
http://www.infoarena.ro/Asociatia-infoarenahttp://www.infoarena.ro/monitor?task=dictree&user=Cristy94http://creativecommons.org/licenses/by-nc/2.5/http://www.infoarena.ro/documentatie/tutorialhttp://creativecommons.org/licenses/by-nc/2.5/