VOI 17 Bài 5 - Xâu đối xứng

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đọc đề gốc tại đây.

Một xâu ký tự được gọi là xâu đối xứng nếu đọc xâu đó từ trái qua phải cũng như đọc nó từ phải qua trái ta thu được cùng một xâu. Một xâu ký tự được gọi là xâu đối xứng cấp ~0~ nếu tồn tại một cách sắp xếp lại các ký tự của nó để thu được một xâu đối xứng.

Một xâu ~s=s_1 s_2 \ldots s_n~ gồm ~n~ ký tự (ta gọi ~n~ là độ dài của xâu ~s~) được gọi là xâu đối xứng cấp ~k~ nếu nó thoả mãn các điều kiện sau:

  1. ~s~ là xâu đối xứng cấp ~0~;
  2. tồn tại ~k~ vị trí ~1 < i_1 < i_2 < \ldots < i_k < n~, sao cho xâu con gồm ~i_j~ ký tự đầu tiên của xâu ~s~ là xâu đối xứng cấp ~0~, ~j = 1, 2, \ldots, k~.

Dễ thấy, nếu một xâu là xâu đối xứng cấp ~k~ thì nó cũng là xâu đối xứng cấp ~m~ với ~0 \le m < k~.

Ví dụ, các xâu ada, abba là các xâu đối xứng; xâu daa là xâu đối xứng cấp 0; xâu abab là xâu đối xứng cấp ~1~ (vị trí thoả mãn định nghĩa là ~i_1 = 3~); xâu ababd là xâu đối xứng cấp ~2~ (~2~ vị trí thoả mãn định nghĩa là ~i_1 = 3~ và ~i_2 = 4~).

Ký hiệu ~S(n, k, \Omega)~ là dãy tất cả các xâu đối xứng cấp ~k~ độ dài ~n~ chỉ gồm các ký tự thuộc tập ký tự ~\Omega~ được liệt kê theo thứ tự từ điển, đánh số bắt đầu từ ~1~.

Ví dụ, với ~n = 3; \; k = 1; \;~ ~\Omega = \{\text{'v', 'n'}\}~, dãy ~S(3, 1, \{\text{'v', 'n'}\})~ gồm 4 xâu được liệt kê theo thứ tự từ điển và đánh số thứ tự bắt đầu từ ~1~ sau đây:

  1. nnn
  2. nnv
  3. vvn
  4. vvv

Yêu cầu: Cho ~n, k, \Omega~ và số nguyên ~t~, hãy đưa ra xâu thứ ~t~ trong dãy ~S(n, k, \Omega)~.

Input

  • Dòng đầu chứa hai số nguyên không âm ~n, k~ ~(k \le n - 2)~;
  • Dòng thứ hai chứa các ký tự của tập ~\Omega~ được ghi nhận bởi một xâu gồm không quá ~5~ chữ cái in thường lấy từ tập ~26~ chữ cái tiếng Anh từ a đến z;
  • Dòng thứ ba chứa số nguyên dương ~t~ (~t~ không lớn hơn số lượng phần tử của ~S(n, k, \Omega)~).

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra xâu thứ ~t~ của dãy ~S(n, k, \Omega)~.

Giới hạn

  • Có ~20\%~ số lượng test thoả mãn điều kiện: ~2 \le n \le 10; \; \Omega = {a, b}~;
  • Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 10; \; k = 0~;
  • Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 50; \; k = 0; \; \Omega = {a, b}~;
  • Có ~20\%~ số lượng test khác thoả mãn điều kiện: ~2 \le n \le 50; \; k = 0;~
  • ~20\%~ số lượng test còn lại thoả mãn điều kiện: ~2 \le n \le 50~.

Sample Input

3 1
vn
2

Sample Output

nnv

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.


There are no comments at the moment.