Mô tả và yêu cầu

Một chuỗi n bit được gọi là “n bit thưa” nếu nó không chứa hai bit 1 liên tiếp.
Yêu cầu: Liệt kê và đếm các chuỗi n bit thưa.

Dữ liệu vào

Từ thiết bị nhập chuẩn chứa 1 số nguyên n.

Dữ liệu ra

Ghi ra thiết bị xuất chuẩn gồm:
- Mỗi dòng một phương án thỏa yêu cầu (chú ý theo thứ tự từ điển).
- Dòng cuối cùng chứa số nguyên d là số các “n bit thưa”.
Các số trên cùng một dòng cách nhau một khoảng trống.

Ví dụ

3

0 0 0
0 0 1
0 1 0
1 0 0
1 0 1
5

Các dãy bit không thỏa yêu cầu đề bài:
0 1 1
1 1 0
1 1 1