NGÔN NGỮ MUMBA

Xem PDF

Nộp bài


Điểm: 10
Thời gian: 1.0s
Bộ nhớ: 64M

Tác giả:
Dạng bài

Mỗi từ trong ngôn ngữ của bộ tộc Mumba hình thành từ các ký tự ab theo quy tắc sau:

  • Không chứa 2 ký tự b liên tiếp,
  • Không có ba từ con giống nhau đứng liên tiếp trong một từ, như vậy aaa không phải là một từ (có 3 từ con a liên tiếp), aabababa cũng không phải là một từ (có 3 từ con ab liên tiếp).

Tất cả các xâu thỏa mãn những điều kiện trên đều là từ trong ngôn ngữ Mumba.

Yêu cầu: Cho số nguyên k(1k105). Hãy xác định số từ trong ngôn ngữ Mumba có độ dài đúng bằng k.

Dữ liệu: Gồm một dòng chứa số nguyên k.

Kết quả: Một số nguyên – kết quả tìm được.

Ví dụ:

Input

Copy
5

Output

Copy
7

Ràng buộc

  • 30% số test ứng 30% số điểm có k20
  • 60% số test ứng 60% số điểm có k25