FIB2 - 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
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
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 ~F_0, F_1, F_2, \dots,~ được xây dựng theo quy tắc sau:
- ~F_0 =~ 'a'
- ~F_1 =~ 'b'
- ~F_n = F_{n-2} + F_{n-1}, n>1~
Yêu cầu: Cho hai số nguyên ~n, k~ (~n\le 45, k~ không vượt quá độ dài xâu ~F_n~). 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 ~F_n~.
Input
- Dòng đầu tiên chứa số nguyên dương ~T~ là số bộ dữ liệu ~(T\le 100)~;
- ~T~ dòng sau, mỗi dòng chứa hai số nguyên ~n, k~.
Output
- Ghi ra ~T~ dòng tương ứng là kết quả của ~T~ bộ dữ liệu đầu vào.
Sample
Input #1
4
0 1
1 1
3 2
7 7
Output #1
1
0
1
3
Problem source: Kc97ble - Free Contest
Bình luận
sao bài này sai test case đúng có 5 cái ta @@