Masala #S013
Fibonacci Total
Fibonacci ketma ketligi:
- \(F_1 = 1\),
- \(F_2 = 2\),
- \(F_i = F_i -_1 + F_i -_2, i > 2\).
Shu ketma-ketlik asosida fibonacci hadlarini ko'rib chiqing va \(S = \{s_1, s_2, ..., s_k\}\) ushbu to'plam elementlari yigindisini toping.
- \(\displaystyle\sum_{I=1}^{K} S_i=n\)
Sizning vazifangiz \(n\) soni uchun fibonacci sonlaridan iborat bo'lgan nechata ketma-ketlik tuzish mumkin ekanligini topishdan iborat.
Kiritish faylida Birinchi qatorda testlar soni \(t(1 ≤ t ≤ 10^5)\)
Har bir test uchub alohida qatorlarda \(n (1 ≤ n ≤ 10^{18})\) butun soni kiritiladi.
Agar siz C++ da bolsangiz, Raqamlarni o'qish yoki yozish uchun %lld spesifikatsiyasidan foydalaning. Tavsiya etilgan oqimlar cin, cout yoki %I64d spetsifikatsiyasi.
Chiqish faylida alohida qatorlarda har bir test uchun javobni chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 13 16 |
3 4 |
1-test:
- n = 13 uchun, S = {13, 5 + 8, 2 + 3 + 8} ketma-ketlik tuzish mumkin.
- n = 16 uchun, S = {3 + 13, 1 + 2 + 13, 3 + 5 + 8, 1 + 2 + 5 + 8} ketma-ketlik tuzish mumkin.
Eslatma:
Agar to'plamda boshqa tuzilgan toplamdagi sonlardan 1 ta bolsa ham farqli son bolsa bu to'plam boshqalaridan farqlanadi. Faqat toplamlardagi sonlarni o'rni almashib kelsa ham ular 1 ta deb hisoblanadi.
Telegram kanalimizga obuna bo'ling