Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó. Cụ thể, các số đầu tiên của dãy Fibonacci là 1, 1, 2, 3, 5, 8, 13, 21,...
Yêu cầu: Cho trước một dãy n số nguyên dương a1, a2, ..., an (1≤ n≤106, 1≤ai≤106 với 1≤ i≤n), em hãy tìm các số Fibonacci xuất hiện trong dãy.
Dữ liệu vào: Đọc từ tệp văn bản FIBO.INP gồm: Dòng đầu tiên gồm số nguyên dương n, dòng tiếp theo gồm n số nguyên dương, các số được viết cách nhau một vài khoảng trống (dấu cách).
Dữ liệu ra: Ghi ra tệp văn bản FIBO.OUT gồm: Dòng duy nhất gồm các số Fibonacci có mặt trong dãy a1, a2, ..., an, các số được viết cách nhau một dấu cách. Nếu không có số nào thì ghi số 0.
|
FIBO.INP |
FIBO.OUT |
|
6 1 20 30 55 20 5 |
1 55 5 |
|
10 2 3 1 4 5 7 13 5 10 14 |
2 3 1 5 13 5 |
|
5 20 9 4 11 7 |
0 |