VM 08 Bài 01 - Bậc Thang - VNOJ: VNOI Online Judge

Trang chủ » Số Bậc Thang Pascal » VM 08 Bài 01 - Bậc Thang - VNOJ: VNOI Online Judge

Có thể bạn quan tâm

VI EN Đăng nhập hoặc Đăng ký

VM 08 Bài 01 - Bậc thang

Xem dạng PDF Gửi bài giải Danh sách bài nộp Bài nộp tốt nhất Đọc lời giải Điểm: 0,06 (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: VNOI Marathon '08 - Round 1/DivBProblem Setter: Ngô Minh Ðức Dạng bài Quy hoạch động Ngôn ngữ cho phép C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.

Sample Input 1

4 2 2 3

Sample Output 1

0

Sample Input 2

90000 1 49000

Sample Output 2

4108266

Bình luận

Hãy đọc nội quy trước khi bình luận.
  • 1 vominhmanh10 đã bình luận lúc 1, Tháng 11, 2025, 10:15

    dp đếm

    import sys input = sys.stdin.read mod = 14062008 def main(n, a): dp = [0] * (n + 1) dp[1] = 1 if 1 not in a else 0 dp[2] = 0 if 2 in a else dp[1] for i in range(3, n + 1): if i in a: dp[i] = 0 else: dp[i] = (dp[i - 1] + dp[i - 2]) % mod return dp[n] data = input().split() n, k = map(int, data[0:2]) a = set(map(int, data[2:2 + k])) print(main(n, a))
  • 0 DAThinh_HuMaDa đã bình luận lúc 29, Tháng 10, 2025, 3:49

    dùng dp là ra

  • 1 ngoccaidu2008 đã bình luận lúc 19, Tháng 9, 2025, 13:49

    bài này hay ấy

  • -2 hieuducle đã bình luận lúc 17, Tháng 8, 2025, 13:41

    include<bits/stdc++.h>

    define ll long long

    using namespace std; const int N = 1e5 + 5; const int MOD = 14062008; ll n , k , dp[N] , a[N]; bool check[N]; int main() { iosbase::syncwith_stdio(false); cin.tie(nullptr);

    for(ll i=1;i<=N;++i) check[i] = true; cin >> n >> k; for(ll i=1;i<=k;++i) { ll x; cin >> x; check[x] = false; } dp[1] = 1; for(ll i=2;i<=n;++i) { if(check[i] == 0) dp[i] = 0; else dp[i] = (dp[i-1] + dp[i-2]) % MOD; } cout << dp[n]; return 0; }

  • -5 pkhoinguyen1106 đã bình luận lúc 11, Tháng 8, 2025, 14:52

    ko đùa đâu nhma ny bn ngol vl

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -30 tandochuyentin2022 đã bình luận lúc 19, Tháng 2, 2025, 13:47

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • 0 vominhmanh10 đã bình luận lúc 1, Tháng 11, 2025, 8:03

      bà giỡn hoài bà ơi

  • -7 NVTai đã bình luận lúc 11, Tháng 2, 2025, 14:46

    bài này tui thấy thuật toán fibonacci áp dụng vào thì nó sẽ không ra đúng đán án, phải biến đổi một chút là dp[2]=1 thì mới đúng, b nào thây như vậy thì upvote cho mình với

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • -5 hahuy0928 đã bình luận lúc 18, Tháng 2, 2025, 17:24

      :)))) may quá

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -6 tanhphungvivo2009 đã bình luận lúc 13, Tháng 1, 2025, 11:54

    bài này dp là được

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -2 nhpnuyn đã bình luận lúc 6, Tháng 11, 2024, 1:40 ← chỉnh sửa →

    bài hay quá

  • -20 kentran232 đã bình luận lúc 16, Tháng 9, 2024, 8:51

    Solution:

    Bai nay de, tu lam nhe! :)

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -8 Soda12 đã bình luận lúc 10, Tháng 8, 2024, 2:52

    hehe

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • 9 hoanglongnguyen9002 đã bình luận lúc 24, Tháng 7, 2024, 13:08 ← chỉnh sửa →

    cho em hoi bai nay lam sao a?

    • -25 hieudeptrai đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa →

      minh khong biet

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

      • -19 sunshine262 đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa →

        minh khong biet

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

        • -15 xingyi đã bình luận lúc 24, Tháng 7, 2024, 13:10 ← chỉnh sửa →

          to khong biet

          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

          • -13 kimchi5e4 đã bình luận lúc 24, Tháng 7, 2024, 13:11 ← chỉnh sửa →

            chiu a!

            Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

            • -15 YoruNiKakeru đã bình luận lúc 24, Tháng 7, 2024, 13:12 ← chỉnh sửa →

              mình chịu bạn ạ

              Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

              • -15 hieuz08 đã bình luận lúc 24, Tháng 7, 2024, 13:13

                cho em hoi lam sao de di' ha` ly

                Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -9 melondepchai đã bình luận lúc 29, Tháng 6, 2024, 5:25

    Fact: ngày 14/06/2008 chứ không phải 16/04/2008 (Lúc đầu tui bị sai như vầy)

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -22 jard đã bình luận lúc 10, Tháng 5, 2024, 11:03

    xin downvote

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -16 how_to_get_her_love999 đã bình luận lúc 5, Tháng 1, 2024, 2:34 ← chỉnh sửa →

    aghhhh

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -12 Cuunon311 đã bình luận lúc 9, Tháng 10, 2023, 18:03

    bai nay hay qua ae enter image description here

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -3 kakapy đã bình luận lúc 9, Tháng 10, 2023, 13:13

    day fibonaci

  • -12 nogo007akapkn đã bình luận lúc 23, Tháng 9, 2023, 3:18

    Spoil: Quy hoach dong voi dp[i] la so cach de den duoc bac thang thu i, dap an la dp[n], voi i la chi so cua cac bac thang bi hong thi dp[i]=0

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • -9 __int128 đã bình luận lúc 22, Tháng 5, 2024, 3:50

      lmao xtz

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -25 reddevils2709 đã bình luận lúc 23, Tháng 2, 2023, 19:31

    bài bậc thang

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

Từ khóa » Số Bậc Thang Pascal