Mảnh Ghép Lời Tiên Tri

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Giáo sư Sybill Trelawney vừa phát hiện $N$ mảnh giấy cổ trong Phòng Tiên Tri tại Bộ Phép Thuật. Mỗi mảnh giấy chứa một đoạn ký tự — là một phần của lời tiên tri vĩ đại. Bà tin rằng lời tiên tri hoàn chỉnh là một xâu ký tự ngắn nhất có thể sao cho mỗi mảnh giấy đều xuất hiện như một xâu con liên tiếp (substring) trong xâu đó.

Hãy giúp Giáo sư Trelawney tìm độ dài của lời tiên tri ngắn nhất chứa tất cả các mảnh giấy.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ — số mảnh giấy.
$N$ dòng tiếp theo, mỗi dòng chứa một xâu ký tự gồm các chữ cái Latin thường — nội dung mảnh giấy thứ $i$ .

Dữ liệu ra

In ra một số nguyên duy nhất — độ dài ngắn nhất của lời tiên tri chứa tất cả các mảnh giấy.

Ràng buộc

$1 \leq N \leq 18$
Mỗi xâu có độ dài từ $1$ đến $1000$
Tổng độ dài tất cả các xâu không quá $10000$
Các xâu chỉ chứa chữ cái Latin thường

Ví dụ

Input	Output	Giải thích
3 loinha nhadoc docduoc	13	Lời tiên tri ngắn nhất là loinhadocduoc (độ dài 13). Xâu này chứa loinha, nhadoc, và docduoc như các xâu con liên tiếp.
4 abc bcd cde dea	6	Lời tiên tri ngắn nhất là abcdea (độ dài 6). Xâu này chứa tất cả 4 mảnh: abc, bcd, cde, dea.

Ghi chú

Lưu ý rằng nếu một mảnh giấy đã nằm trọn bên trong một mảnh khác, ta không cần thêm bất kỳ ký tự nào cho mảnh đó. Ví dụ, nếu có hai mảnh "abcde" và "bcd", thì "abcde" đã chứa "bcd" nên lời tiên tri ngắn nhất chỉ cần dài 5.

Bình luận

Không có bình luận tại thời điểm này.