Người Gửi: Dương Lee
- Problem:
Tí đố Tèo giải một đoạn mật thư. Đầu vào là một chuỗi kí tự có độ dài bằng N và có M kí tự ‘#’. Với mỗi kí tự ‘#’, có K kí tự sẵn có để thay thế cho nó. Như vậy, nếu thử chọn sẽ có tất cả K^M trường hợp. Đáp án của mật thư là xâu có thứ tự bằng X theo thứ tự từ điển trong tập hợp tất cả các khả năng trên.
Việc thay thế lần lượt từng kí tự vào kí tự ‘#’ của mật thư sẽ sinh ra rất nhiều các trường hợp. Tèo nghĩ một lúc lâu mà vẫn chưa ra. Các bạn hãy giúp Tèo nhé.
Input
Dòng đầu tiên gồm 4 số nguyên N, M, K và X (1 <= N <= 500, 1 <= M <= N, 1 <= K <= 26, 1 <= X <= 10^9).
Dòng tiếp theo chứa xâu S có độ dài bằng N, là đoạn mật thư mà Tí gửi cho Tèo, chỉ bao gồm các chữ cái thường và kí tự ‘#’.
M dòng tiếp theo, dòng thứ i gồm K kí tự, là các khả năng có thể thay thế cho kí tự ‘#’ thứ i trong xâu S.
Output
n ra xâu có số thứ tự bằng X theo thứ tự từ điển.
Example:
Input
9 2 3 7
bi#omke#i
abc
efd
Output:
bicomkedi
Input
4 1 2 2
#iek
ab
Output:
biek
- Solution:
Input
4 1 2 2
#iek
ab
Output:
biek
Giải thích test 2: Có tất cả 2 xâu là aiek và biek, trong đó biek là xâu có STT bằng 2.
- Đầu tiên cần phải sắp xếp cho các string cần chọn tăng dần (theo thứ tự từ điển).
- Với mỗi một số x cho trước, kí tự # tìm được (từ cuối lên) và dãy kí tự điền vào tương ứng. Để xác định xem nó là kí tự nào chỉ cần lấy (X%M) thì sẽ xác định được vị trí kí tự cần điền vào.
(Nói tóm lại sử dụng phép chia ma trận để xác định vị trí hàng, cột).