STEPS (BẬC THANG) – VSTEPS – SPOJ | LÀM HẾT MÌNH

Trang chủ » Số Bậc Thang Pascal » STEPS (BẬC THANG) – VSTEPS – SPOJ | LÀM HẾT MÌNH

Có thể bạn quan tâm

LÀM HẾT MÌNH – VÌ CHÍNH MÌNH Bỏ qua nội dung ← GẶM CỎ – VMUNCH – SPOJ CƠ SỐ H – BASE H – SPOJ →

STEPS (BẬC THANG) – VSTEPS – SPOJ

Đăng trong 01/06/2014 bởi connhangheovodanh

ĐỀ BÀI :

STEPS (BẬC THANG) – VSTEPS – SPOJ

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.

Dữ liệu

  • 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 ≤ k < n ≤ 100000).

  • 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.

Kết qủa

In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008.

Ví dụ

Dữ liệu 4 2 2 3 Kết qủa 0 Dữ liệu 90000 1 49000 Kết qủa 4108266

THUẬT TOÁN :

Bài này dùng QHĐ.

Trước tiên tạo mạng lưu trạng thái của một bậc thang xem nó sống hay chết. Ta dùng mảng yes[i]. Nếu yes[i] = true thì không hỏng và ngược lại. Thứ hai, ta gọi F[i] là số cách leo lên bậc thang thứ i. Đương nhiên nếu nó hỏng thì chẳng có cách nào để leo lên và f[i] = 0.

Ban đầu f[1] = 1 vì nó đang đứng ở đó. F[2] tùy thuộc nó chết hay sống mà f[2] 0 or 1. Xét tại một bước thứ i. Nếu như không có đường đến nó thì f[i] = 0. Ngược lại nếu trước đó bậc i-1 chết thì bậc i không thể lên từ i-1, bậc i-2 sống thì ta có một con đường duy nhất lên i là từ i-2 và f[i] = f[i-2] else nếu i-1 sống và i-2 chết thì cũng vậy f[i] = f[i-1] else nữa cả hai cùng sống thì f[i] = f[i-1] + f[i-2]. Nếu cả hai cùng chết thì đương nhiên chẳng có đường nào lên nổi n

Đây là code của mình, các bạn lấy tham khảo :

CODE :

#include <iostream> #include <fstream> #include <cmath> #include <algorithm> #include <cstring> #include <string> #include <cstdlib> #include <cstdio> #include <stack> #include <queue> #include <vector> #include <set> #include <map>   using namespace std;   const long base = 14062008; long       n,k,t,f[150000]; bool       yes[150000] = {true};   int main() {     scanf("%li %li",&n,&k);     for (long i=0;i<=n;i++) yes[i] = true;     for (long i=1;i<=k;i++)     {         scanf("%li",&t);         yes[t] = false;     }     f[0] = 0;     f[1] = 1;     if (yes[2]) f[2] = 1; else f[2] = 0;     for (long i=3;i<=n;i++)         if (not(yes[i]))   f[i] = 0; else         if ((not(yes[i-1])) and (yes[i-2])) f[i] = f[i-2] % base; else         if ((not(yes[i-2])) and (yes[i-1])) f[i] = f[i-1] % base; else f[i] = (f[i-1] % base + f[i-2] % base) % base;     printf("%li",f[n]);     return 0; }

Chia sẻ:

  • X
  • Facebook
Thích Đang tải...

Có liên quan

Bài này đã được đăng trong Bài tập, Quy hoạch động, Spoj. Đánh dấu đường dẫn tĩnh. ← GẶM CỎ – VMUNCH – SPOJ CƠ SỐ H – BASE H – SPOJ →

Bình luận về bài viết này

Δ

  • Tìm kiếm cho:

  • Thống kê

    • 290 972 lượt xem

  • Bài viết mới

    • SPOJ – Tin mật – SEC 02/04/2015
    • SPOJ – Chuỗi từ – CHAIN2 30/03/2015
    • SPOJ – ACM – ACMNB 27/03/2015
    • SPOJ – Chuỗi ốc – BEADSNB 27/03/2015
    • Codeforces – Tutorial For Contest Nowruz challenge 25/01/2015
    • SPOJ – Phần tử thứ K – YPKTH 24/01/2015
    • SPOJ – Cuộc đấu cân não – NCOB 20/01/2015
    • SPOJ – Time Travel – TTRAVEL 20/01/2015
    • SPOJ – Tập hợp động – CPPSET (cơ bản về set) 20/01/2015
    • SPOJ – Dãy số may mắn – NKLUCK 15/01/2015
    • SPOJ – Above the Median – KMEDIAN 13/01/2015
    • SPOJ – LUBENICA – LUBENICA 11/01/2015
    • SPOJ – Lowest Common Ancestor – LCA 11/01/2015
    • SPOJ – Tăng tốc mạng máy tính – NETACCEL 11/01/2015
    • SPOJ – Floyd hoặc Dijkstra ( Cơ bản ) – FLOYD 11/01/2015

  • Follow

    Enter your email address to follow this blog and receive notifications of new posts by email.

    Địa chỉ email:

    Theo dõi

    Tham gia cùng 26 người đăng ký khác

  • Lượt nhấp chuột hàng đầu

    • mediafire.com/download/ct…
  • Tìm kiếm cho:

  • Liên kết

    • Tạo tài khoản
    • Đăng nhập
    • RSS bài viết
    • RSS bình luận
    • WordPress.com
LÀM HẾT MÌNH – VÌ CHÍNH MÌNH Blog tại WordPress.com.
  • Bình luận
  • Đăng lại
  • Theo dõi Đã theo dõi
    • LÀM HẾT MÌNH - VÌ CHÍNH MÌNH
      • Đã có 26 người theo dõi Theo dõi ngay
    • Đã có tài khoản WordPress.com? Đăng nhập.
    • LÀM HẾT MÌNH - VÌ CHÍNH MÌNH
    • Theo dõi Đã theo dõi
    • Đăng ký
    • Đăng nhập
    • URL rút gọn
    • Báo cáo nội dung
    • Xem toàn bộ bài viết
    • Quản lý theo dõi
    • Ẩn menu
%d Tạo trang giống vầy với WordPress.comHãy bắt đầu

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