COCI 2016/2017 - Contest 1 - Vjestica

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 1
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Người anh hùng, nhà thám hiểm trẻ tuổi Matej sau một chuyến hành trình đầy cam go đã đặt chân đến địa điểm cuối cùng của định mệnh - lãnh địa của mụ phù thuỷ độc ác Marija. Để hoàn thành chuyến phiêu lưu của mình, Matej sẽ phải giải quyết câu đố mà mụ Marija đưa ra cho anh.

Để giải quyết được câu đố của mụ, người anh hùng của chúng ta cần làm quen với một cấu trúc dữ liệu có tên là cây tiền tố (prefix tree/trie).

Một cây tiền tố là một cấu trúc dữ liệu giúp biểu diễn tất cả tiền tố của các từ trong một tập hợp từ. Cây tiền tố có những tính chất như sau:

  • Mỗi cạnh của cây được gán bằng một chữ cái ở trong bảng chữ cái.
  • Gốc của cây tiền tố là một nút rỗng
  • Các nút còn lại của cây biểu diễn một tiền tố khác rỗng. Mà tiền tố của một nút thu được bằng cách ghép các chữ cái trên các cạnh nối từ gốc đến nút đó với nhau (các chữ cái cũng ghép với nhau theo thứ tự từ gốc đến nút đó).
  • Không tồn tại hai cạnh xuất phát từ cùng một nút duy nhất mà được gán bằng cùng một chữ cái (cách này sẽ giảm thiểu số lượng nút cần để biểu diễn các tiền tố)

Cây tiền tố cho các từ: "A", "to", "tea", "ted", "ten" và "inn".

Chỉ khi Matej nắm bắt được cây tiền tố là gì thì thử thách mới thực sự bắt đầu!

Mụ phù thuỷ đưa cho anh ấy ~N~ từ tiếng Anh in thường. Thử thách sẽ rất dễ nếu bà ta muốn biết số lượng các nút trên cây tiền tố tạo ra từ các từ đã cho. Tuy nhiên, bà ta muốn làm khó người anh hùng bằng cách yêu cầu Matej tính số lượng nút tối thiểu của cây tiền tố có thể có sau khi hoán vị các chữ cái của mỗi từ đã cho một cách tuỳ ý.

Hãy giúp Matej tìm đáp án cho thử thách này!

Input

  • Dòng đầu chứa số nguyên ~N\ (1 \leq N \leq 16)~.
  • ~N~ dòng tiếp theo mỗi dòng chứa một từ in thường với cái chữ cái trong từ thuộc bảng chữ cái tiếng Anh.

Tổng độ dài của tất cả các từ sẽ nhỏ hơn ~1 000 000~

Output

Một dòng duy nhất ghi ra đáp án cho câu đố của mụ phù thuỷ Marija.

Sample 1

Input
3
a
ab
abc
Output
4

Sample 2

Input
3
a
ab
c
Output
4

Sample 3

Input
4
baab
abab
aabb
bbaa
Output
5

Giải thích

Ở ví dụ ~3~: Tất cả các từ có thể hoán vị thành từ "aabb", vì vậy số lượng nút tối thiểu của cây tiền tố là 5 (4 nút lá + 1 nút gốc - chứa tiền tố rỗng)


Comments

Please read the guidelines before commenting.


There are no comments at the moment.