La chaîne de référence
On vous donne une liste de
n chaînes, chacune composée de lettres minuscules de l’alphabet latin. Nous définirons une chaîne de référence comme étant une chaîne s, formée de lettres minuscules de l’alphabet latin et du caractère #, telle que, pour chaque chaîne de la liste, on puisse trouver un certain indice i dans s où ≠ #, et en sélectionnant tous les indices depuis i jusqu’à la prochaine occurrence de # (sans l’inclure), on obtienne cette chaîne. De plus, la chaîne de référence doit toujours se terminer par le caractère #.Écrivez un programme qui détermine la longueur de la plus courte chaîne de référence satisfaisant cette condition à partir de la liste de chaînes donnée.
Entrée
La première ligne d’entrée contient un entier
n (1 ≤ n ≤ 100 000), représentant le nombre de chaînes dans la liste.Les
n lignes suivantes contiennent les chaînes. Chaque chaîne est formée de lettres minuscules de l’alphabet latin et a une longueur d’au plus 10.Sortie
Le programme doit afficher un seul entier, qui correspond à la longueur de la plus courte chaîne de référence satisfaisant la condition.
Exemples
Input | Output |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Explications
- Exemple 1 : l’une des plus courtes chaînes de référence possibles est «
ground#profound#wound#».
- Exemple 2 : l’une des plus courtes chaînes de référence possibles est «
ab#bc#cd#».
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB