Xâu Fibonacci 2

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

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 fo, f1, f2, ... được xây dựng theo quy tắc sau:

• fo = a

• f1 = b

• fn = fn-2 + fn-1, với n > 1

Yêu cầu: Cho hai số nguyên dương 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


Đầu vào: Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 100) là số lượng test cần xử lý t dòng sau mỗi dòng chứa hai số nguyên dương n và k

Đầu ra: Với mỗi test đưa ra số lượng ký tự a xuất hiện trong k ký tự đầu tiên của xâu fn trên một dòng


Input:
4
0 1
1 1
3 2
7 7
Output:
1
0
1
3

Giải thích:

• fo = a

• f1 = b

• f2 = ab

• f3 = bab


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.