Đếm xâu nhị phân không có hai ký tự 1 kề nhau
Nhiều bài quy hoạch động cần nhớ trạng thái của ký tự cuối cùng chứ không chỉ vị trí đang xét.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, strings.
Nội dung đề bài
Mô tả bài toán
Nhiều bài quy hoạch động cần nhớ trạng thái của ký tự cuối cùng chứ không chỉ vị trí đang xét. Bài này là ví dụ nhỏ nhất: khi ghép thêm một ký tự, ta phải biết ký tự vừa thêm là 0 hay 1 để biết có được phép thêm 1 nữa hay không.
Yêu cầu
Đếm số xâu nhị phân độ dài n mà không có hai ký tự 1 nào nằm cạnh nhau. Ví dụ với n = 3 có 5 xâu: 000, 001, 010, 100, 101; xâu 011, 110, 111 bị loại.
Quy ước nộp bài
Nộp tệp solution.cpp đọc n từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Một dòng duy nhất chứa số nguyên n (1 <= n <= 40).
Output
- Một số nguyên trên một dòng là số xâu hợp lệ. Với n = 40 đáp án là 267914296.
Ràng buộc
- Mỗi ký tự chỉ là 0 hoặc 1.
- Chỉ cần in số lượng, không cần liệt kê các xâu.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
1
Output
2
Ví dụ 2
Input
2
Output
3
Giải thích
Bốn xâu độ dài 2 là 00, 01, 10, 11, nhưng 11 bị loại nên còn 3. In ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
