Dãy số Fibonaci là dãy số tự nhiên gồm có hai số đầu tiên là 1, các số tiếp theo có quy luật là bằng tổng hai số liền kề trước số đó.
Cho trước một số nguyên không âm N

Yêu cầu: Kiểm tra xem có thể phân tích N thành dãy các số Fibonaci liên tiếp bắt đầu từ 1 hay không?

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương N (0 < N < 10⁹).

Dữ liệu ra:

• Dòng 1: Ghi dãy số được phân tích ra thành các số fibonaci từ số đầu tiên, kể cả số dư ra
• Dòng 2: Ghi chữ YES nếu phân tích được, ghi NO nếu không phân tích hết được

15

1 1 2 3 5 3
NO

20

1 1 2 3 5 8
YES