.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » descfib

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
descfib


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Gigel a aflat din “sursa sigura” ca orice numar natural se poate descompune ca suma de termeni neconsecutivi ai sirului Fibonacci  si ca o astfel de descompunere este unica. Desi s-a chinuit cateva nopti bune sa demonstreze acest lucru el nu a ajuns la nici o concluzie. Totusi un program care poate sa gaseasca descompunerea unui numar dat i-ar fi de mare ajutor avand o mica sansa sa se prinda de modul in care aceasta descompunere este construita uitandu-se pe cateva exemple.

Cerinta

Scrieti programul de care Gigel are nevoie.

Date de intrare

Pe prima linie a fisierului descfib.in se afla un numar natural N de a carui descompunere este interesat Gigel.

Date de iesire

Fisierul descfib.out contine pe prima linie un numar intreg K reprezentand numarul de termeni din descompunerea lui N. Pe urmatoarele K linii se afla cate un termen din descompunere, in ordine crescatoare.

Restrictii si precizari

  • 1 <= N <= 10100
  • Pentru 40% din teste N <= 1018
  • Pentru problema "descfib" sirul Fibonacci se va considera definit in urmatorul mod: F1 = 1, F2 = 2 si F(n+1) = F(n) + F(n - 1) cu n > 1
    (prin F(i) se intelege al i-lea termen al sirului).
    In consecinta, primii termeni ai sirului vor fi:
    1, 2, 3, 5, 8, 13, 21, ...

Exemplu

descfib.in

descfib.out

17

3
1
3
13

Silviu Ionut Ganceanu
Universitatea Politehnica Bucuresti
Contact: tzi_ganci@hotmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: otilia, tvshow, algola, bifo, pal, evantai, treegame
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, tub, m01, soldati1, euclid, mutare, munte1, bifo, banda10, sg1, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre Fibonacci: fib, grupe, euclid, fibo, gramada, vanatoare, sirul, fibo1, taler, aliniere, subm, flori2, prime2
Despre Inducţie matematică: 2sir, h, gray, poligon, patrate1, set, suma1, mutare, sir1, prieteni1, excursie1, galax, prieteni2, peg, perfect, borcane, regine, comoara2, domino, arctir, partitie, acoperire1, xpn
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
Despre structura repetitiva: cifre1, super, schimb, jeton, taxe, romane, mobile, cuburi3, tzigla, morse, powerpuff, multimi, ucif, tabel, ocr, numere7, cifre2, piramida, vraji, reforma, cartonas, cabina, case, desen2, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, paranteze, tort, copaci1, ogorul, puncte3, efort, muzeu, smith, biliard, palc, prod3, fazanr, cadouri, bursa, meteo, prodmax, zar, tren4, lego, maraton1, cluburi, domino1, jump, alo, cifra1, case1, brazi, greiere, divizori, pitag, porumb, secv9, divk, rachete, pin, sumacifre, aritm, psp, triplu, triunghi3, cmmdcsecv, ssmax, ape, furnici1, domino2, acoperire1, ore, pegals, b2k, sumdivprod, subsecvmax, dale, bancomat, sume4, alice, porumb1, albine2, culegere, stele1, medalion, cifreco, meteo1, unupatru, xyz, vistiernic, chibrituri, bete1, greieri, interviu, prieten, prize, conturi, numere12, martisoare, piramide, pagini, punctul, tablita, pavare1, ordine, covor1, speciale, echer, numere13
surse trimise | ajutor