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

VM 08 Bài 01 - Bậc thang

View as PDF

Submit solution

All submissions

Read editorial

Points: 0.02 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem source:

VNOI Marathon '08 - Round 1/DivBProblem Setter: Ngô Minh Ðức

Problem type

Allowed languages

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

Sample Input 2

90000 1
49000

Sample Output 2

Comments

Comments

Please read the guidelines before commenting.

vominhmanh10 commented on Nov. 1, 2025, 10:15 a.m.

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))

1

DAThinh_HuMaDa commented on Oct. 29, 2025, 3:49 a.m.

dùng dp là ra

1

ngoccaidu2008 commented on Sept. 19, 2025, 1:49 p.m.

bài này hay ấy

-1

hieuducle commented on Aug. 17, 2025, 1:41 p.m.

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 commented on Aug. 11, 2025, 2:52 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-30

tandochuyentin2022 commented on Feb. 19, 2025, 1:47 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

0

vominhmanh10 commented on Nov. 1, 2025, 8:03 a.m.

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

-7

NVTai commented on Feb. 11, 2025, 2:46 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-5

hahuy0928 commented on Feb. 18, 2025, 5:24 p.m.

:)))) may quá

This comment is hidden due to too much negative feedback. Show it anyway.

-6

tanhphungvivo2009 commented on Jan. 13, 2025, 11:54 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-2

nhpnuyn commented on Nov. 6, 2024, 1:40 a.m. ← edited →

bài hay quá

-20

kentran232 commented on Sept. 16, 2024, 8:51 a.m.

Solution:

Bai nay de, tu lam nhe! :)

This comment is hidden due to too much negative feedback. Show it anyway.

-8

Soda12 commented on Aug. 10, 2024, 2:52 a.m.

hehe

This comment is hidden due to too much negative feedback. Show it anyway.

9

hoanglongnguyen9002 commented on July 24, 2024, 1:08 p.m. ← edited →

cho em hoi bai nay lam sao a?

-25

hieudeptrai commented on July 24, 2024, 1:10 p.m. ← edited →

minh khong biet

This comment is hidden due to too much negative feedback. Show it anyway.

-19

sunshine262 commented on July 24, 2024, 1:10 p.m. ← edited →

minh khong biet

This comment is hidden due to too much negative feedback. Show it anyway.

-15

xingyi commented on July 24, 2024, 1:10 p.m. ← edited →

to khong biet

This comment is hidden due to too much negative feedback. Show it anyway.

-13

kimchi5e4 commented on July 24, 2024, 1:11 p.m. ← edited →

chiu a!

This comment is hidden due to too much negative feedback. Show it anyway.

-15

YoruNiKakeru commented on July 24, 2024, 1:12 p.m. ← edited →

mình chịu bạn ạ

This comment is hidden due to too much negative feedback. Show it anyway.

-15

hieuz08 commented on July 24, 2024, 1:13 p.m.

cho em hoi lam sao de di' ha` ly

This comment is hidden due to too much negative feedback. Show it anyway.

-9

melondepchai commented on June 29, 2024, 5:25 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-23

jard commented on May 10, 2024, 11:03 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-16

how_to_get_her_love999 commented on Jan. 5, 2024, 2:34 a.m. ← edited →

aghhhh

This comment is hidden due to too much negative feedback. Show it anyway.

-12

Cuunon311 commented on Oct. 9, 2023, 6:03 p.m.

bai nay hay qua ae

This comment is hidden due to too much negative feedback. Show it anyway.

-3

kakapy commented on Oct. 9, 2023, 1:13 p.m.

day fibonaci

-12

nogo007akapkn commented on Sept. 23, 2023, 3:18 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.