Dãy nhị phân
Xem dạng PDF
Gửi bài giải
Điểm:
600,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
là một học sinh thông minh, cần cù chịu khó nhưng khá lười biếng. Một hôm, được thầy cho bài tập như sau: Cho trước số nguyên dương ~N~ ~(N~ ~≤~ ~50)~. Hãy đếm số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có ~2~ kí tự ~1~ nào đứng cạnh nhau. Nhưng vì tối qua mãi chơi Free Fire đến khuya nên sáng nay bạn ấy không còn đủ tỉnh táo để làm bài tập, các bạn hãy giúp giải bài tập này nhé!
Input
- Số nguyên dương ~N~ duy nhất.
Output
- Số nguyên duy nhất là số lượng xâu nhị phân có độ dài ~N~ mà trong xâu đó không có 2 kí tự 1 nào đứng cạnh nhau.
Ví dụ
Input
3
Output
5
- Giải thích: Với ~N~ ~=~ ~3~, ta có ~5~ dãy ~000, 001, 010, 100, 101~.
Subtask:
- Subtask ~1~ (40% số điểm): ~N~ ~≤~ ~20~.
- Subtask ~2~ (60% số điểm): ~20~ ~<~ ~N~ ~≤~ ~50~.
Bình luận
Cần cù nhưng lười biếng ?!
can cu nhung luoi bieng 🐧
fibo là full
là sao bạn?
là dùng công thức dp theo kiểu của fibonaci á bạn
nhưng mình đang bảo ở chỗ cần cù nhưng lười biếng mà bạn
bạn minh phan nứ lúc cần cù nhưng lúc lại lười biếng, rút gọn lại nó v á =)))
cần cù là mp tự nhét dô chứ mp làm gì cần cù 🐧