Bạn vừa phát minh ra một phiên bản sửa đổi nhẹ của thuật toán nén run-length encoding (RLE), gọi là PermRLE.

Để nén một chuỗi, thuật toán này chọn một hoán vị của các số nguyên từ \(1\) đến \(k\), áp dụng hoán vị này cho \(k\) chữ cái đầu tiên của chuỗi đã cho, sau đó cho khối \(k\) chữ cái tiếp theo, và cứ tiếp tục như vậy. Độ dài của chuỗi phải chia hết cho \(k\). Sau khi hoán vị tất cả các khối, chuỗi mới được nén bằng RLE, được mô tả sau đây.

Việc áp dụng hoán vị \(p\) cho một khối \(k\) chữ cái có nghĩa là đặt chữ cái thứ \(p[1]\) của khối này vào vị trí đầu tiên, sau đó là chữ cái thứ \(p[2]\) vào vị trí thứ hai, và cứ tiếp tục như vậy. Ví dụ, áp dụng hoán vị \(\{3,1,4,2\}\) cho khối "abcd" sẽ thu được "cadb". Áp dụng nó cho chuỗi dài hơn "abcdefghijkl" theo từng khối sẽ thu được "cadbgehfkilj".

Chuỗi đã hoán vị sau đó được nén bằng run-length encoding. Để đơn giản, chúng ta sẽ coi kích thước nén của chuỗi là số lượng các nhóm chữ cái bằng nhau liên tiếp. Ví dụ, kích thước nén của "aabcaaaa" là 4; nhóm đầu tiên trong bốn nhóm là một nhóm gồm hai chữ cái "a", sau đó là hai nhóm "b" và "c" mỗi nhóm chỉ chứa một chữ cái, và cuối cùng là một nhóm chữ cái "a" dài hơn.

Rõ ràng, kích thước nén có thể phụ thuộc vào hoán vị được chọn. Vì mục tiêu của các thuật toán nén là giảm thiểu kích thước của văn bản nén, nhiệm vụ của bạn là chọn hoán vị mang lại kích thước nén nhỏ nhất có thể và xuất ra kích thước đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test sẽ chứa \(k\). Dòng thứ hai sẽ chứa \(S\), chuỗi cần được nén.

Dữ liệu ra

Đối với mỗi bộ test, bạn nên xuất ra một dòng chứa "Case #\(X\): \(Y\)" (dấu ngoặc kép để rõ ràng) trong đó \(X\) là số thứ tự của bộ test và \(Y\) là kích thước nén tối thiểu của \(S\).

Ràng buộc

• \(N = 20\)
• \(S\) sẽ chỉ chứa các chữ cái tiếng Anh viết thường từ 'a' đến 'z'
• Độ dài của \(S\) sẽ chia hết cho \(k\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(2 \le k \le 5\)
• \(1 \le \text{length of } S \le 1000\)
• Large dataset (Test set 2 - Hidden):
• \(2 \le k \le 16\)
• \(1 \le \text{length of } S \le 50000\)

Đ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
4
abcabcabcabc
3
abcabcabcabc

Case #1: 7
Case #2: 12

Nguồn

Google Code Jam 2008, Vòng 2, bài PermRLE.

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