Xâu con liên tiếp

View as PDF

Submit solution

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

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

Một xâu ký tự được gọi là xâu ký tự hằng nếu mọi ký tự của xâu đều giống nhau. Ví dụ, p, vv hay hhh là các xâu ký tự hằng, còn gspvhcute thì không.

Một xâu con liên tiếp của xâu ký tự ~s = s_1 s_2 \ldots s_n~ là xâu ký tự có dạng ~s_l s_{l+1} \ldots s_{r-1} s_r~ với ~1 \leq l \leq r \leq n~. Ví dụ, xâu ppvhhh có ~21~ xâu con liên tiếp, trong đó có ~10~ xâu ký tự hằng: h xuất hiện ~3~ lần, phh xuất hiện ~2~ lần, mỗi xâu pp, vhhh xuất hiện ~1~ lần.

Cho hai số nguyên ~n~ và ~k~, xét tập hợp ~\Omega~ gồm các xâu ký tự ~s~ chỉ gồm chữ cái in thường có chính xác ~n~ xâu con liên tiếp là xâu ký tự hằng. Hãy sắp xếp các xâu ký tự trong ~\Omega~ theo thứ tự từ điển, và in ra xâu ký tự thứ ~k~ trong tập hợp này.

Input

File input gồm ~3~ câu hỏi, mỗi câu hỏi được thể hiện bởi hai số ~n~ và ~k~ được viết trên một dòng với ~1 \leq n \leq 10^7~ và ~1 \leq k \leq 3 \cdot 10^{18}~. Dữ liệu vào đảm bảo số ~k~ không lớn hơn lực lượng của tập hợp ~\Omega~ được định nghĩa ở trên.

Output

Với mỗi câu hỏi, in ra xâu ký tự cần tìm trên một dòng.

Giới hạn

  • Subtask ~1~ (~10~ điểm): ~n \leq 2~
  • Subtask ~2~ (~14~ điểm): ~n \leq 4~
  • Subtask ~3~ (~20~ điểm): ~n \leq 15~ và ~k \leq 10^6~
  • Subtask ~4~ (~16~ điểm): ~k = 1~
  • Subtask ~5~ (~20~ điểm): ~n \leq 100~
  • Subtask ~6~ (~20~ điểm): Không có ràng buộc gì thêm

Sample Input 1

1 1
1 2
1 3

Sample Output 1

a
b
c

Sample Input 2

3 1
3 2
3 3

Sample Output 2

aa
aba
abc

Sample Input 3

2 168
3 9899
4 43749

Sample Output 3

gs
pvh
cute

Sample Input 4

22 7
19 97
56 23

Sample Output 4

aaaaaah
aaaaabaev
aaaaaaaaaax

Comments

Please read the guidelines before commenting.


There are no comments at the moment.