Hướng dẫn giải của Tổng số Fibonacci (đề Phú Yên 2021)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần biểu diễn số ~N~ thành tổng ít số hạng nhất, mỗi số hạng là một số Fibonacci và các số hạng khác nhau. Dãy Fibonacci có ~1, 1, 2, 3, 5, 8, \ldots~; số ~1~ xuất hiện hai lần nên chỉ lấy một lần: tập số dùng được là ~1, 2, 3, 5, 8, \ldots~.
Lưu ý thứ tự in: đề ghi "từ bé đến lớn" nhưng ví dụ và dữ liệu chấm in theo thứ tự giảm dần (ví dụ ~129 = 89 + 34 + 5 + 1~ in ra 89 34 5 1), nên chương trình in theo thứ tự giảm dần như ví dụ.
Sub 1: Vét cạn theo tập con — ~O(2^k)~ với ~k~ là số Fibonacci không vượt quá ~N~, dùng khi ~N \le 100~
Liệt kê mọi tập con của các số Fibonacci không vượt quá ~N~. Giữ lại tập có tổng bằng ~N~ và ít phần tử nhất. Nếu chỉ nộp sub này: đúng 23/30 test (đúng hết các test trong miền, 7 test lớn bị quá giờ).
Sub 2: Tham lam (Zeckendorf) — ~O(\log N)~
Lấy liên tục số Fibonacci lớn nhất không vượt quá phần còn lại, trừ đi rồi lặp lại. Cách biểu diễn này (Zeckendorf) dùng ít số hạng nhất. Bẫy cần chú ý: không lấy trùng số 1; sinh dãy Fibonacci đủ lớn (đến khoảng ~2 \cdot 10^6~ là đủ). Nếu chỉ nộp sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
main đọc ~N~ từ file, sinh dãy Fibonacci khác nhau. Nếu ~N \le 100~ gọi sub1, còn lại gọi sub2. Đầu main có freopen vì máy chấm đọc/ghi file BAI3.INP, BAI3.OUT.
#include <bits/stdc++.h>
using namespace std;
long long N;
vector<long long> fib; // cac so Fibonacci khac nhau: 1, 2, 3, 5, 8, ... (bo ban sao 1 o F_1, F_2)
// Sub 1: vet can - thu moi tap con cua cac so Fibonacci nho hon N, lay tap co it phan tu nhat co tong bang N.
void sub1() {
vector<long long> small;
for (long long f : fib) if (f <= N) small.push_back(f);
int k = small.size();
int bestCnt = INT_MAX;
vector<long long> best;
for (int mask = 0; mask < (1 << k); mask++) {
long long s = 0;
int c = 0;
for (int i = 0; i < k; i++)
if (mask >> i & 1) { s += small[i]; c++; }
if (s == N && c < bestCnt) {
bestCnt = c;
best.clear();
for (int i = 0; i < k; i++)
if (mask >> i & 1) best.push_back(small[i]);
}
}
// in theo thu tu giam dan, dung nhu mau va du lieu cham (khac voi chu "tu be den lon" trong de)
reverse(best.begin(), best.end());
for (size_t i = 0; i < best.size(); i++)
cout << best[i] << (i + 1 < best.size() ? " " : "\n");
}
// Sub 2: tham lam Zeckendorf - moi lan lay so Fibonacci lon nhat khong vuot qua N.
// Cach nay cho it so hang nhat, va ket qua duoc in tu nho den lon.
void sub2() {
vector<long long> res;
long long rem = N;
for (int i = (int)fib.size() - 1; i >= 0 && rem > 0; i--) {
if (fib[i] <= rem) {
res.push_back(fib[i]);
rem -= fib[i];
}
}
// res dang o thu tu giam dan (lay tu lon den nho), in ra luon
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 < res.size() ? " " : "\n");
}
int main() {
freopen("BAI3.INP", "r", stdin); // may cham doc/ghi file
freopen("BAI3.OUT", "w", stdout);
cin >> N;
// Sinh cac so Fibonacci khac nhau den 2*10^6 (bo so 1 lap lai)
fib.push_back(1);
fib.push_back(2);
while (fib.back() <= 4000000) fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
if (N <= 100) sub1(); // du lieu nho: vet can
else sub2(); // du lieu lon: tham lam
return 0;
}
Bình luận