Trong quá trình luyện tập cho cuộc thi học sinh giỏi sắp tới, Hùng được thầy giáo giao cho thử sức giải bài toán nén xâu kí tự (chỉ gôm các kí tự latin in hoa) sau đây:
Phép cộng trên hai xâu và , kí hiệu là , được hiểu là ghép xâu liền sau xâu . Xuất phát từ hai xâu , và số nguyên , xâu được tạo theo luật sau (còn được gọi là luật tựa Fibonacci): .
Ví dụ: với hai xâu AB, C và ta có:
AB, C, CAB, CABC, CABCCAB.
Giả sử xâu độ dài là xâu được tạo theo luật trên từ hai xâu xuất phát có độ dài tương ứng là . Như vậy, là xâu gồm kí tự đầu tiên của xâu và là xâu gồm kí tự tiếp theo của xâu . Xâu có thể được nén thành bộ vì từ thông tin và ta có thể khôi phục được xâu theo luật trên. Ví dụ, xâu CABCCAB có thê được nén thành bộ .
Một xâu bất kì có độ dài cũng có thể được nén theo cách như trên. Với hai số nguyên dương , gọi là xâu gồm ; kí tự đầu tiên của xâu và là xâu gồm kí tự tiếp theo trên xâu . Khi đó, xâu có thể được nén thành bộ . Tuy nhiên, từ thông tin và ta có thể không khôi phục được chính xác xâu . Do đó, người ta đánh giá độ lỗi của phương pháp nén xâu này như sau. Với bộ , tạo xâu với nhỏ nhất mà độ dài lớn hơn hoặc bằng theo luật tựa Fibonnaci từ hai xâu xuất phát . Độ lỗi của việc nén xâu được tính bằng số lượng vị trí mà khác với , trong đó và tương ứng là kí tự thứ của xâu và xâu với .
Ví dụ, với và , xâu CABACC có độ dài được nén thành bộ , sau đó tạo ra xâu CABCCAB. Khi đó, độ lỗi của việc nén xâu là đo có hai kí tự ở các vị trí thứ và thứ của và là khác nhau.
Nhận thấy rằng, kí tự đầu tiên của xâu ảnh hưởng rất lớn đến độ lỗi của việc nén xâu. Vì vậy, người ta tiến hành thay đổi không quá kí tự trong kí tự đầu tiên của xâu để biến xâu thành xâu sao cho độ lỗi của việc nén xâu là nhỏ nhất. Việc thay đổi một kí tự là thay kí tự đó bởi một kí tự khác.
Yêu cầu: Cho các số nguyên và xâu , hãy tìm cách thay đổi không quá kí tự trong kí tự đầu tiên của xâu để biến xâu thành xâu sao cho độ lỗi của việc nén xâu là nhỏ nhất.
Dữ liệu vào:
Dòng thứ nhất chứa bốn số nguyên cách nhau bởi dấu cách ;
Dòng thứ hai chứa xâu độ dài , xâu chỉ gồm các kí tự thuộc tập kí tự chữ cái latin in hoa (từ A đến Z).
Dữ liệu ra:
Ghi ra một số nguyên là độ lỗi nhỏ nhất tìm được.
Ví dụ:
Dữ liệu vào:
6 2 1 1
CABAAC
Dữ liệu ra:
1
Giái thích:
Trong ví dụ trên, cách thay tối ưu nhất là thay kí tự đầu tiên của xâu thành A để nhận được xâu AABAAC. Với và , xâu được nén thành bộ , ta tạo ra xâu AABAAAB. Khi đó, độ lỗi của việc nén xâu bằng do kí tự ở vị trí thứ của và là khác nhau.
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: và xâu chỉ gồm hai kí tự A và B;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
