시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 36 | 11 | 11 | 61.111% |
Vera is learning about the longest common subsequence problem.
A string is a (possibly empty) sequence of lowercase letters. A subsequence of a string S is a string obtained by deleting some letters of S (possibly none or all). For example “vra”, “a”, “”, and “vera” are all subsequences of “vera”. The longest common subsequence (LCS) of two strings, A and B, is a string that is a subsequence of both A and B that has the maximum length among all strings that are a subsequence of both A and B. There could be multiple LCS for two given strings. For example a LCS of “vera” and “eats” is “ea”.
For homework she was given two strings A and B, both of length N and she had to determine the length of the LCS of A and B. She determined the answer to be K but lost B. Given A and K, help her find a possible value of B. It is possible that Vera may have made a mistake and no such B exists, in that case output “WRONGANSWER"(without quotes).
The input will be in the format:
N K A
Constraints:
Output one line consisting of the string B of N lowercase letters, or “W RONGANSW ER” if no B is valid. If there are multiple correct B output any of them.
4 2 vera
eats
4 5 vera
WRONGANSWER
For the first example, another possible answer is “uber”.