Xâu con liên tiếp

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 0.5s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.