Bậc thang
Xem dạng PDF
Gửi bài giải
Điểm:
14,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
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc. Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng). Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.
Input
- Dòng đầu tiên: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng ~(0 \le k < n \le 10^5)~.
- Dòng thứ hai: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.
Output
- In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008
Examples
Input
4 2
2 3
Output
0
Input
90000 1
49000
Output
4108266
Bình luận
Bước 1: Khởi tạo mảng b và a
a là một mảng chứa k phần tử không được sử dụng.
Bước 2: Đọc dữ liệu đầu vào
Chương trình đọc hai số nguyên n và k từ người dùng. n là số phần tử mà bạn muốn sắp xếp và k là số lượng phần tử không được sử dụng (các phần tử trong danh sách a).
Bước 3: Không sử dụng các phần tử từ danh sách a
Với mỗi phần tử a[i] trong danh sách a, chương trình đặt b[a[i]] bằng 0, vì không có cách sắp xếp nào có thể sử dụng phần tử a[i].
Bước 4: Tính giá trị b bằng phương pháp Fibonacci
Chương trình sử dụng một vòng lặp từ 2 đến n để tính giá trị b[i] dựa trên giá trị b[i-1] và b[i-2], giống như phương pháp Fibonacci.
Bước 5: In đáp án
Viết solution ngắn lại tí em nhé. Hướng dẫn tổng quát!
thaybeo
HUnGbEO
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
im
nì ga
shutup
im
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
duahauhavefatpussy
bích