MKOKOS - KOKOS
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
English Vietnamese
Một tập có N từ, mỗi từ có độ dài 2K kí tự.
Đồ thị có hướng với mỗi đỉnh chứa 1 kí từ được gọi là "kokos" nếu, với mỗi từ trong tập, có 1 đường đi mà nhãn các định của đường đi này tạo thành từ đó. Ngoài ra, mọi đỉnh trên đường đi này phải thỏa mãn:
· Bậc vào của đỉnh đầu tiên là 0.
· Bậc vào của K-1 đỉnh tiếp theo là 1.
· Bậc ra của K-1 đỉnh tiếp theo là 1.
· Bậc ra của đỉnh cuối cùng là 0.
Nghĩa là các đường đi này chỉ có thể phân nhánh theo K kí tự đầu tiên và gặp nhau ở K kí tự cuối cùng. Một "kokos" là cực tiểu nếu số đỉnh của nó là nhỏ nhất có thể.
Cần xác định số đỉnh này.
Ví dụ về kokos cực tiểu (tập các từ của ví dụ thứ 3):
Một cách biểu diễn khác như sau:
Tuy nhiên, nó không là kokos vì các đường đi gặp nhau ở kí tự thứ 4 (D), và rẽ nhanh ở kí tự thứ 6 (E).
Input
Dòng đầu gồm 2 số nguyên N và K, 1 ≤ N ≤ 10 000, 1 ≤ K ≤ 100.
N dòng tiếp theo mỗi dòng chứa một từ, chỉ gồm chữ in hoa tiếng Anh, ('A'-'Z').
Output
Số đỉnh trong kokos cực tiểu.
Sample
input
2 4
ABCDEFGH
EFGHIJKL
output
16
input
4 3
XXZZXX
XXYYZZ
AABBCZ
ABCZZZ
output
18
input
4 4
ABCDEFGH
ACBDEFGH
ABDCFEHG
EFEFFEGH
output
23
- Người up: vdmedragon
- Nguồn bài: COI 06