Cho một DFA đầy đủ. Liệt kê các chuỗi được chấp nhận theo thứ tự: độ dài tăng dần, cùng độ dài thì theo thứ tự từ điển (a<b<…). Hãy in ra chuỗi thứ K (đánh số từ 1). Nếu chuỗi rỗng là chuỗi thứ K, in -. Nếu ngôn ngữ có ít hơn K chuỗi, in -1. Dùng đếm số chuỗi chấp nhận theo độ dài rồi tìm kiếm tham lam.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
2 2
1 0
0 1
0
1 1
3
Output:
ba
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).
Sau khối DFA là một dòng chứa số nguyên K.1 ≤ n ≤ 200, 1 ≤ k ≤ 26, 1 ≤ K ≤ 10^9.
In chuỗi được chấp nhận thứ K; - nếu là chuỗi rỗng; -1 nếu không đủ.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
3
Đầu ra:
ba
Giải thích:
Đang tải editor...