Câu chuyện

Giáo sư Loony, một người bạn thân của tôi, xông vào văn phòng tôi với khuôn mặt đỏ bừng và trông rất giận dữ. Điều đầu tiên ông ấy thốt ra là "Thật là tệ hại cho mấy tay sản xuất điện thoại. Tôi đã cố gắng gửi một tin nhắn văn bản, và tôi mất hơn mười phút để gõ một dòng tin nhắn duy nhất." Tôi cố gắng trấn an ông ấy: "Nhưng có chuyện gì vậy? Tại sao ông lại mất nhiều thời gian đến thế?" Ông ấy tiếp tục: "Anh không thấy sao?! Cách họ sắp xếp các chữ cái thật là lộn xộn! Tại sao 's' lại là chữ cái thứ 4 trên phím của nó? Còn 'e' nữa? Tại sao nó không phải là chữ cái đầu tiên trên phím? Tôi phải nhấn phím '7' BỐN lần để gõ một chữ 's'? Thật là điên rồ!"

"Bình tĩnh đi bạn tôi," tôi nói, "Sơ đồ này đã được sử dụng từ rất lâu rồi, ngay cả trước khi tin nhắn văn bản được phát minh. Họ phải giữ nó như vậy."

"Đó không phải là lý do," mặt ông ấy càng lúc càng đỏ hơn. "Đã đến lúc phải thay đổi tất cả những thứ này. Ngay từ đầu nó đã là một ý tưởng ngớ ngẩn rồi. Và nhân tiện, tại sao họ chỉ đặt các chữ cái trên 8 phím? Tại sao không dùng cả 12 phím? Và tại sao chúng phải liên tiếp nhau?"

"Ừm... tôi... không... biết," tôi trả lời.

"Được rồi, thế là đủ rồi. Những người đó rõ ràng là kém năng lực. Tôi chắc chắn rằng ai đó có thể nghĩ ra một sơ đồ tốt hơn."

Tôi có thể thấy ông ấy là một trong những người như vậy. Những người phàn nàn về vấn đề, nhưng không bao giờ thực sự cố gắng giải quyết nó.

Trong bài toán này, bạn được yêu cầu đưa ra cách sắp xếp các chữ cái lên các phím tốt nhất để tối thiểu hóa số lần nhấn phím cần thiết để gõ một tin nhắn. Bạn sẽ được cho số lượng phím, số lượng chữ cái tối đa có thể đặt trên mỗi phím, tổng số chữ cái trong bảng chữ cái và tần suất của mỗi chữ cái trong tin nhắn. Các chữ cái có thể được đặt ở bất kỳ đâu trên các phím và theo bất kỳ thứ tự nào. Mỗi chữ cái chỉ có thể xuất hiện trên một phím. Ngoài ra, bảng chữ cái có thể có nhiều hơn 26 chữ cái (đây không phải là tiếng Anh).

Để tham khảo, bàn phím điện thoại hiện tại trông như thế này:

key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz

Lần nhấn đầu tiên của một phím sẽ gõ chữ cái đầu tiên. Mỗi lần nhấn tiếp theo sẽ chuyển sang chữ cái kế tiếp. Ví dụ, để gõ từ "snow", bạn cần nhấn "7" bốn lần, tiếp theo là "6" hai lần, tiếp theo là "6" ba lần, và cuối cùng là "9" một lần. Tổng số lần nhấn phím là 10.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ thử nghiệm \(N\). Tiếp theo là \(N\) trường hợp. Mỗi trường hợp gồm hai dòng. Trên dòng đầu tiên, chúng ta có số lượng chữ cái tối đa có thể đặt trên một phím (\(P\)), số lượng phím khả dụng (\(K\)) và số lượng chữ cái trong bảng chữ cái của chúng ta (\(L\)), tất cả cách nhau bởi dấu cách đơn. Dòng thứ hai có \(L\) số nguyên không âm. Mỗi số đại diện cho tần suất của một chữ cái nhất định. Số đầu tiên là số lần chữ cái thứ nhất được sử dụng, số thứ hai là số lần chữ cái thứ hai được sử dụng, và cứ tiếp tục như vậy.

Dữ liệu ra

Với mỗi trường hợp, bạn nên xuất ra dòng sau:

Case #x: [minimum number of keypad presses]

cho biết số lần nhấn bàn phím để gõ tin nhắn cho cách sắp xếp tối ưu.

Ràng buộc

• \(P \times K \ge L\)
• \(0 \le\) Tần suất của mỗi chữ cái \(\le 1000000\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N \le 10\)
• \(1 \le P \le 10\)
• \(1 \le K \le 12\)
• \(1 \le L \le 100\)
• Large dataset (Test set 2 - Hidden):
• \(1 \le N \le 100\)
• \(1 \le P \le 1000\)
• \(1 \le K \le 1000\)
• \(1 \le L \le 1000\)

Đ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ụ

2
3 2 6
8 2 5 2 4 9
3 9 26
1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

Case #1: 47
Case #2: 397

Nguồn

Google Code Jam 2008, Vòng 1C, bài Text Messaging Outrage.

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