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