xaufibo - Xâu Fibonacci
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: vinhntndu

Xâu Fibonacci thường được sử dụng để rèn luyện kỹ năng xử lý khi giới thiệu các giải thuật xử lý xâu. Xét dãy xâu F0, F1, F2  , . . . xây dựng theo quy tắc sau:

  • F0 =’a’
  • F1 = ‘b’
  • Fn = Fn-2 + Fn-1, n>1

Yêu cầu: Cho hai số nguyên n và k (0 ≤ n≤ 45, k không vượt quá độ dài xâu Fn). Hãy xác định số lượng ký tự a xuất hiện trong k ký tự đầu tiên của xâu Fn

Dữ liệu: Vào từ file FIB2.INP

  • Dòng đầu ghi số nguyên T là số test cần xử lý (1 <= T <=100)
  • Mỗi dòng trong T dòng sau ghi hai số n và k cách nhau ít nhất một dấu cách.

Kết quả: Kết quả ghi vào file văn bản FIB2.OUT, ứng với mỗi test trên một dòng dưới dạng một số nguyên.

Ví dụ:

FIB2.INP

FIB2.OUT

4

0     1

1     1

3     2

7     7

1

0

1

3

Ví dụ

Back to Top