Vua Mật Mã
Xem PDFSau khi đả bại sứa xanh justys, hiện đang đối mặt với vua mật mã . cho tên người yêu cũ thứ 96 của mình, và muốn tìm một xâu kí tự có thứ tự từ điển nhỏ nhất và không nhỏ hơn tên người yêu cũ của . Tuy nhiên, vì căm ghét người yêu cũ, muốn chỉ sử dụng không quá \(cnt_{c}\) kí tự \(c\). Đương nhiên đã đưa ra câu trả lời trong 6ms. Các bạn hãy thử sức giải câu đố của vua mật mã nhé.
Input
-
Dòng đầu tiên chứa 1 số nguyên dương \(n \ (n \leq 10^{3})\) là độ dài tên người yêu cũ của vua mật mã.
-
Dòng tiếp theo một xâu kí tự \(S\) là tên người yêu cũ của , tên chỉ chứa các kí tự la tinh thường.
-
Dòng tiếp theo chứa 26 số \(cnt_{c_{i}}\), \(c_{i}\) là kí tự la tinh thường thứ \(i\), \(cnt_{c}\) là số kí tự \(c\) tối đa mà được phép sử dụng.
Output
- In ra một xâu kí tự thoả mãn yêu cầu của vua mật mã . In ra \(-1\) nếu không có xâu kí tự thoả mãn.
Scoring
-
Subtask \(1\) (\(10\%\) số điểm): \(n \leq 20\), \(cnt_{c_{i}} \leq 10^{5}\)
-
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\), \(\Sigma cnt_{c_{i}} \leq 10\)
-
Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000\), \(cnt_{c_{i}} \leq 10^9\) và vua mật mã chỉ cho phép sử dụng tối đa 2 kí tự.
-
Subtask \(4\) (\(50\%\) số điểm): \(n \leq 10^{3}\), \(cnt_{c_{i}} \leq 10^{9}\)
Example
Test 1
Input
2
aa
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1Output
abNote
Ở ví dụ 1, mỗi kí tự chỉ được dùng 1 lần, riêng kí tự \(u\) được dùng 2 lần. Một số xâu thoả mãn là \(amisuper\), \(amibest\) , \(amiop\) , \(cuomngu\) , \(cuomnguthe\) , \(cuomgathiesu\), \(ab\). Xâu \(ab\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(aa\).
Test 2
Input
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1Output
azNote
Ở ví dụ 2, kí tự a được dùng 1 lần, kí tự z được dùng 1 lần. Các xâu thoả mãn là \(a\) , \(az\) , \(z\) , \(za\). Xâu \(az\) có thứ tự từ điển nhỏ nhất và lớn hơn xâu \(amideptrai\). Lưu ý rằng \(a\) có thứ tự từ điểm nhỏ hơn \(amideptrai\) nên không hợp lệ.
Test 3
Input
10
amideptrai
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Output
-1Note
Ở ví dụ 3, kí tự a được dùng 1 lần, do đó chỉ có 1 xâu thoả mãn là \(a\). Xâu này có thứ tự từ điển nhỏ hơn \(amideptrai\), do đó không hợp lệ
Bình luận
vì sao test ví dụ 2 thì "az" lại có thứ tự từ điển lớn hơn "amideptrai" vậy mn?
giải quyết bài trên ami ó vũ khí gì
anh đã update, cảm ơn em.
Chữ \(cuomgathietsu\) có 2 chữ t mà trong test chỉ cho 1 chữ t thôi
Giải thích ví dụ sai rồi anh ami ơi.