10579 - Fibonacci Numbers

[htl]

On the ranklist I discovered that so many people spent much less time and memory to run the prog. But I took much time and memory doing this. Could someone teach me how to accelerate the prog?

[Rajib]

This is a simple string addition problem. You can faster the string addition by converting the base of huge integer and then do the add operation.

For an example,

65535 (dec) == FFFF (hex)

65535 (dec) + 65535 (dec) will take much operation than,
FFFF (hex) + FFFF(hex)

so if you convert the base from 10 to 1000000 then all the addition will take too less time and also use less memory.

Hope it will help you. [Goodluck ]

[htl]

It means that if I should make a multiplication table for any base I wanna to convert to? Could you give me more information on bigint? Thanks!

[Rajib]

Dear, bigint is nothing but your own defined class or any function that is capable to do som basic mathematical operation like 'add','sub','mul' or 'div';

You need to create your own bigint class where after taking the input you just convert the base from 10 to any reasonable large base (like 10000/1000000 etc)

You can try it yourself or search from internet. Google is a greate search tool for any one.

Very simple...

[htl]

I have tried addition calculation... Thanks..

[Jemerson]

I've discovered that the input number will never be bigger than 2000, this may also help your task of saving time.

[Jewel of DIU]

I have got WA in this problem. I want to know where is my fault.
Can anyone give me some Input-Output?

[wook]

3
7
9
15
26
91
908
1000
1001
2304
4050
4193

2
13
34
610
121393
4660046610375530309
2578055988351964688851245616452378875719427641782287809992231431923843111069006580781633989295161822889603301376722022739968120221030578561210113091181592243452683913671969416353921002961821
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
14389249193537346502772224660708391363974074224031165912511479986580413455592697676914098196280915634676814357764797796942757230167365636396228901819502777532782328499457335604959606923828176768890848934755946589659477195179289391585256010310590494251015374450071673506809289150888345551908510946718650559880347211375167967789813677421584153943165542945205422383470837969241770259019562079511490632284912702227205106485993243621727709777670796030653557386201124687733827484661705728
1123202367623691261472030947771824186445260714537445712410256586471967236352291455801691514949255846581399973115710358926004651635047407184799329328989748065460285968261548861925648078998008181316297740277246645230394972544448254612674839210880442203332168128734296836122701052803797574505265110491255939403095871421808363237251856837517894699972365428779784292432297603041699095552507479932821733017660861892747638625038617049973658235291801281090157941335879116361450476037528254627554369665897104921158024449083658762362139974683623035017745632716104877481148730001915570810847526219616770426518352830069616082849656432219010775200392753506835342086443195821041446143489630027196184160781123260471558771127231037208858656094228992343338974059087636425522200212138074097016132561592809167266053191213128750901078513253981075981821469485715525400
862363896158625849322546953399018044181135441009671254965428796843040993211093580110466764876635079048946988620366663256320679675634239143756153127684654998531593831884601779881114883075935860881108085007792279472013554545982893377091468133787003475477691114259942422726963433153634152960067659555212802149299494192643002527851062706879115817643909995640618257353375929372304050728942984986046148086511706061881068074246289206305375108769274655613187442575760420296678910628009192976187263217820973561804809523441240821638349545282386425044301454564033378068406054639587554048013663557003113350396512223211376528626425122277887301040503900060857792006056120599761772998119676414908876088535154845461595894580939772195282890809946110200862040471362079017650045651131104911867358973519539292179931730248667177204356801300694698721906166042232375319434232840275606978693365941213

and, if n is 0, my programs exit the loop.

you need calculate about N < 4800, it will be of 1000 digits.

[20717TZ]

0 should not be in the test data;
The maximum input: 4786 (f(4786) has 1000 digits, while f(4787) has 1001 digits)

Test Input:

Code: Select all

4786
3
100
20
1
2
3
4
4781
43
44
45
46

Test Output

Code: Select all

7334343300431526745413249208471480941295886039383885689591799012660621316779395823705306935954440374490983316440510938218661503030861630551548176293222468430475826259959800604212901428982055681829150950655199287783857015061224226795482474623367665222282256870316117093830732812895097667473105049114270817452107418279883991688450006170770502566063032564075310632474734425490689190635259549767940099905087501320929296630972279603414930997444279094039374065272740853520039785786698227588316593293922583225068083713333591230083257890903615803904675715141475535706043142298866792045298371160569065663936383352746627653451155462689725430610815806257367133656040401322717863284076339742756245203855814663113490689862210696900867531084265725317796456979714878328669946807443728887797839435463413795912940497316758611168447311213734925988635812151655063724137755355835867847379508102339675238232695173896823234061425238260852508144856714319522307480482321929193614716737343149471726333522305539123082795222023
2
354224848179261915075
6765
1
1
2
3
661337322839244020529448762061498838625822185407709121508540998594682904585308540198620399347330470400653280666540992810413273565832926917994398713638718230004471776413151146318909185589434770973461837586080318941036906375808818987789429626217366616261579890860369055555894732519548901040157604298546742957666096845809463021127999592568557636384690462092341124092401245911116667639704650585763476554594656814646920798543755041993472555505701157143290739289844688760895075749533130953287080934600205342326904398216342904642143410026582439596278979961166556037913414174756579068802168337413360918567937945101952123966744780579475400056938418442029794142856905251486526028946063939727834195575354173400454719814829506586601492013100468780852140836021109820860257494909387619656513364393990237289782342713423952649505274336811640790273740875206602634583227097792146230883268422965993230492657630338344967767776216497296016612316692840479306680187737608910337658122657075262622220319456797676633847360981
433494437
701408733
1134903170
1836311903