Cho số nguyên n. Hãy liệt kê tất cả các xâu có đúng n ký tự, trong đó mỗi ký tự thuộc tập {a, b, c}. Danh sách phải được sắp theo thứ tự từ điển tăng dần.
Input
Dòng duy nhất chứa số nguyên n.
Output
In mỗi xâu hợp lệ trên một dòng, theo thứ tự từ điển.
Constraints
1≤n≤8.
Scoring
Subtask 1 (50%): n≤5.
Subtask 2 (50%): Không có giới hạn bổ sung.
Example
Test 1
Input
2
Output
aa
ab
ac
ba
bb
bc
ca
cb
cc
Giải thích: Có 32=9 xâu. Thử ký tự đầu rồi ký tự sau theo thứ tự a,b,c tạo đúng thứ tự từ điển được hiển thị.
Lời giải tóm tắt
Ý tưởng: Xây xâu từ trái sang phải. Ở mỗi vị trí, thử lần lượt a, b, c, rồi đệ quy sang vị trí kế tiếp. Khi đã điền đủ n ký tự, in xâu hiện tại.
Ý tưởng: Do các nhánh luôn được thử theo thứ tự tăng của ký tự, toàn bộ lá của cây đệ quy cũng xuất hiện theo thứ tự từ điển; không cần sinh xong rồi sắp xếp.
Chứng minh tính đúng đắn: Mỗi xâu hợp lệ xác định duy nhất một đường đi dài n trong cây lựa chọn: nhánh ở độ sâu i là ký tự thứ i của xâu. Thuật toán thử đủ ba nhánh ở mọi độ sâu nên mọi xâu đều được sinh. Hai đường đi khác nhau tạo hai xâu khác nhau, vì vậy không có kết quả trùng. Thứ tự duyệt a, b, c tại vị trí khác nhau đầu tiên bảo đảm thứ tự từ điển.
Độ phức tạp: Có 3^n xâu và mỗi xâu dài n, nên thời gian kể cả xuất dữ liệu là O(n·3^n); bộ nhớ phụ O(n).