Gagan vừa nhận được một email từ người bạn Jorge. Email chứa thông tin quan trọng, nhưng không may nó đã bị lỗi khi gửi: tất cả các khoảng trắng đều bị mất, và sau khi xóa các khoảng trắng, một số chữ cái đã bị thay đổi thành các chữ cái khác! Tất cả những gì Gagan có bây giờ là một chuỗi \(S\) gồm các ký tự viết thường.

Bạn biết rằng email ban đầu được tạo ra từ các từ trong từ điển được mô tả bên dưới. Bạn cũng biết rằng các chữ cái đã bị thay đổi sau khi các khoảng trắng được loại bỏ, và khoảng cách giữa các chỉ số của bất kỳ hai chữ cái bị thay đổi nào không nhỏ hơn \(5\). Ví dụ, chuỗi "code jam" có thể đã trở thành "codejam", "dodejbm", "zodejan" hoặc "cidejab", nhưng không thể là "kodezam" (vì khoảng cách giữa chỉ số của thay đổi "k" và thay đổi "z" chỉ là \(4\)).

Số lượng chữ cái tối thiểu có thể đã bị thay đổi là bao nhiêu?

Từ điển

Từ điển chứa \(W\) từ có độ dài ít nhất là \(1\) và tối đa là \(10\) ký tự viết thường và được cung cấp ở đầu tệp dữ liệu vào. Nó không phải là từ điển của bất kỳ ngôn ngữ tự nhiên nào, mặc dù nó có chứa một số từ tiếng Anh. Từ điển là giống nhau cho tất cả các bộ test trong cùng một tệp dữ liệu vào. Từ điển được đưa ra theo thứ tự tăng dần về mặt từ điển và không chứa các từ trùng lặp.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng từ trong từ điển, \(W\). Mỗi dòng trong \(W\) dòng tiếp theo chứa một chuỗi các ký tự viết thường a-z đại diện cho một từ trong từ điển.
Dòng tiếp theo của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bao gồm một dòng duy nhất chứa một chuỗi \(S\), bao gồm các ký tự viết thường a-z.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng chữ cái tối thiểu có thể đã bị thay đổi để tạo ra \(S\).

Ràng buộc

• \(W = 521196\).
• Mỗi từ trong từ điển chứa ít nhất 1 và tối đa 10 ký tự viết thường.
• Từ điển được sắp xếp theo thứ tự từ điển tăng dần.
• Từ điển không chứa các từ trùng lặp.
• Tổng số ký tự trong từ điển là 3323296.
• \(S\) là hợp lệ: có thể tạo ra nó bằng phương pháp mô tả ở trên.

Phân nhóm

• Test set 1 (Visible):

  • \(1 \le T \le 20\).
  • \(1 \le\) độ dài của \(S \le 50\).

  • Test set 2 (Hidden):

  • \(1 \le T \le 4\).

  • \(1 \le\) độ dài của \(S \le 4000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

9
aabea
bobs
code
in
jam
oo
operation
production
system
4
codejam
cxdejax
cooperationaabea
jobsinproduction

Case #1: 0
Case #2: 2
Case #3: 1
Case #4: 1

Nguồn

Google Code Jam 2013, Vòng 1B, bài Garbled Email.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.