Elearning CodePath – CTP Online Judge

Tổng Fibonacci

SUMFIBO

🟢 Hard #General #Greedy

### 📌 Thông tin chung

---
### 📝 Định nghĩa

**Dãy số Fibonacci** ($F_i$) là dãy số được định nghĩa theo công thức:
* $F_1 = 1$, $F_2 = 1$.
* $F_i = F_{i-1} + F_{i-2}$, với $i > 2$.

Bảng giá trị:

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | $\dots$ |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $F_i$ | 1 | 1 | 2 | 3 | 5 | 8 | 13 | $\dots$ |

Yêu cầu: Hãy biểu diễn một số tự nhiên $N$ thành tổng ít nhất các số Fibonacci khác nhau.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `SUMFIBO.INP`:

* Chứa số nguyên $N$.

Giới hạn:
* $1 \le N \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `SUMFIBO.OUT` biểu diễn số $N$ thành tổng ít nhất các số Fibonacci. Các số này được ghi trên một dòng theo thứ tự từ lớn đến bé và cách nhau một dấu cách.

---
### ✨ Ví dụ

| Input (`SUMFIBO.INP`) | Output (`SUMFIBO.OUT`) |
| :---: | :---: |
| `2` | `2` |
| `29` | `21 8` |

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | $1 \le N \le 10^4$ |
| $50\%$ | $10^4 < N \le 10^9$ |

✅ Đã AC: 10 / 21 submissions