Tổng các số Fibonaci

HSG Lâm Đồng 2011 - Bài 2/3
Dãy Fibonaci là dãy gồm các số: 1, 1, 2, 3, 5, 8, .... được xác định bởi công thức sau:
          F1=1, F2=1, Fi=Fi-1+Fi-2 với i>2.
Em hãy biểu diễn một số tự nhiên N thành tổng của ít nhất các số Fibonaci khác nhau.
Dữ liệu vào: cho file FIBO.INP chứa số N (N <= 2000000000)
Dữ liệu ra: ghi ra file FIBO.OUT biểu diễn số N thành tổng của ít nhất các số Fibonaci khác nhau.
Ví dụ:
      FIBO.INP           FIBO.OUT
         129                 129 = 89 + 34 + 5 + 1

Hoặc
      FIBO.INP           FIBO.OUT
           8                       8 = 8