Hỏi đáp

Chia sẻ kiến thức, cùng nhau phát triển

giúp với ạ

14:54 01-09-2022 131 lượt xem 0 bình luận 10:02 02-09-2022

 Giả sử chiếc cầu gỗ này đã được lắp ghép từ N miếng gỗ theo thứ tự từ 1 đến N; vì lâu ngày nên hiện tại đã có một số K miếng gỗ đã bị hỏng không thể bước đi trên nó được. Tý đố Tèo là hãy cho biết có bao nhiêu cách để Tèo xuất phát từ đầu cầu bên này (tức là đứng tại miếng gỗ đầu tiên, là miếng gỗ không hề bị hỏng) mà có thể đi đến được đầu cầu bên kia (tức là đến miếng gỗ thứ N) sao cho mỗi lần bước đi Tèo chỉ được phép bước lên 1 bước hoặc là nhảy lên lần hai  bước (mỗi bước ứng với một miếng gỗ dùng để lắp trên cầu).

Dữ liệu vào: file văn bản Caycau.inp với :

  • Dòng đầu tiên: gồm 2 số nguyên N và K, là số miếng gỗ cần lắp của cây cầu và số miếng gỗ bị hỏng (0 ≤ K < N ≤ 20)
  • Dòng thứ hai: gồm K số nguyên cho biết chỉ số thứ tự của các miếng gỗ bị hỏng theo thứ tự tăng dần.

Dữ liệu ra : file văn bản Caycau.out với:

  • Ghi ra một số nguyên duy nhất là số cách đi, nếu không có cách đi thì ghi 0

Ví dụ:

Caycau.inp1

Caycau.out

Caycau.inp2

Caycau.out

5   1

4

2

7   2

2   3

0

  • Giải thích:

Test 1: có 2 cách đi đó là 1->2->3->5 và 1->3->5

      Test 2 : 0 có cách đi, vì xuất phát từ 1 nhưng miếng gỗ 2,3 đều hỏng nên không thể bước đi được.

viết chương trình với c++ giúp ạ

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập

Câu hỏi mới nhất