Bài 3: (6,0 điểm) XÂU NHỊ PHÂN
Xét các xâu nhị phân độ dài N được thành lập như sau:
- Bắt đầu là xâu gồm N bit 0.
- Xâu nhị phân tiếp theo được tạo thành từ xâu nhị phân trước đó bằng cách tìm bit 0 đầu tiên tính từ phải sang trái đổi thành bit 1 và đổi tất cả các bit bên phải bit vừa thay đổi đó thành bit 0. Ví dụ: xâu tiếp theo của xâu 0100111 là xâu 0101000.
- Lặp lại cho đến khi tất cả N bit đều là bit 1. Ví dụ: Với N = 3, ta có: 000 -> 001 -> 011 -> 100 -> 101 -> 110 -> 111
Sắp xếp các xâu N bit này theo thứ tự từ điển và đánh số thứ tự từ 0 đến hết.
Thứ tự từ điển được tính như sau:
Với hai xâu nhị phân A và B có độ dài N:
- Xâu A được gọi là nhỏ hơn xâu B nếu như bit khác nhau đầu tiên tính từ trái sang phải của xâu a là nhỏ hơn của xâu B.
- Xâu A và xâu B là bằng nhau nếu tất cả các bit của hai xâu tương ứng là như nhau.
Yêu cầu: Cho hai số tự nhiên N và Km(3 ≤ N ≤ 1000, 0 ≤ K ≤ 2N). Hãy tìm xâu nhị phân độ dài N có thứ tự từ điển là K.
Dữ liệu vào: Cho từ file văn bản BL3.INP gồm hai dòng:
- Dòng đầu ghi số N
- Dòng thứ hai ghi số K
Kết quả: Ghi ra file văn bản BL3.OUT gồm dãy N bit tương ứng là xâu nhị phân độ dài N có thứ tự từ điển là K