| ENG RUS | Timus Online Judge |
Обсуждение задачи 1462. Золото дядюшки СкруджаVedernikoff 'Goryinyich' Sergey (HSE: АОП) 2 ADMINS: ban the following user(s) for multiple accounts and flooding testing queue [1] // Задача 1462. Золото дядюшки Скруджа 17 окт 2015 21:56 Kolega FrigATE Mister IPRIT Jogn Doe Jogn Doe2 Jogn Doe3 John Doe 4 John Doe 5 Vladimir Yakovlev (USU) Re: 2 ADMINS: ban the following user(s) for multiple accounts and flooding testing queue // Задача 1462. Золото дядюшки Скруджа 18 окт 2015 14:20 Flooding submissions were cleaned out Edited by author 18.10.2015 14:20 Krayev Alexey (PSU) 0.046s. Who's better? (-) [8] // Задача 1462. Золото дядюшки Скруджа 19 авг 2006 20:30 xurshid_n Re: 0.046s. Who's better? (-) // Задача 1462. Золото дядюшки Скруджа 21 окт 2006 18:18 Please, send me your solution or algorithm!!! my email: xujand000@rambler.ru Vladimir Yakovlev (USU) Did you use FFT? (-) [4] // Задача 1462. Золото дядюшки Скруджа 23 окт 2006 15:25 Edited by author 23.10.2006 19:00 Krayev Alexey (PSU) Re: Yes (-) // Задача 1462. Золото дядюшки Скруджа 23 окт 2006 17:45 xurshid_n What is FFT? (-) [2] // Задача 1462. Золото дядюшки Скруджа 26 окт 2006 18:40 Todor Tsonkov Re: What is FFT? (-) [1] // Задача 1462. Золото дядюшки Скруджа 3 ноя 2006 02:41 I'm also interested in a c++ solution of this problem, please send to tabledott@gmail.com Vedernikoff Sergey Re: What is FFT? (-) // Задача 1462. Золото дядюшки Скруджа 16 ноя 2006 15:30 Simple problem... FFT can be used to solve it, but for what purpose??? [SPbSU ITMO] WiNGeR Re: 0.046s. Who's better? (-) [1] // Задача 1462. Золото дядюшки Скруджа 28 ноя 2006 09:03 0.031 ;) vindex Re: 0.046s. Who's better? (-) // Задача 1462. Золото дядюшки Скруджа 2 дек 2010 12:17 [url=http://www.stratomedia.co.il]בניית אתרים[/url] [url=http://www.vindex.co.il]בעלי מקצוע[/url] [url=http://moverexpert.com]moving[/url] [url=http://www.vindex.co.il/%D7%94%D7%95%D7%91%D7%9C%D7%AA_%D7%93%D7%99%D7%A8%D7%95%D7%AA_%D7%94%D7%95%D7%91%D7%9C%D7%95%D7%AA_%D7%9E%D7%A9%D7%A8%D7%93%D7%99%D7%9D_%D7%94%D7%A2%D7%91%D7%A8%D7%AA_%D7%93%D7%99%D7%A8%D7%94/ ]הובלות[/url] Todor Tsonkov How to improve my Algo. I got TL on test 4 [21] // Задача 1462. Золото дядюшки Скруджа 12 авг 2006 19:35 I try to find fib(2*n-2)/fib(n-2) but I get TL on test 4, my algo is linear so I couldn't pass the TL, I wonder is the direct algo for finding fib(n-2) and fib(2*n-2) better, because I couldn't implement it :) VALERO Re: How to improve my Algo. I got TL on test 4 [13] // Задача 1462. Золото дядюшки Скруджа 12 авг 2006 19:40 i have tl too, but i find that fib(2*n-2)/fib(n-2)=fib(n+1)+fib(n-1) ^) but i have tl ( Mafia {Toropov, Isenbaev, Oparin} SPb IFMO Re: How to improve my Algo. I got TL on test 4 [12] // Задача 1462. Золото дядюшки Скруджа 12 авг 2006 19:48 fib(n) could be evaluated in O(log n) multiplication operations. Todor Tsonkov Re: How to improve my Algo. I got TL on test 4 [11] // Задача 1462. Золото дядюшки Скруджа 12 авг 2006 19:55 Well, my idea was to evaluate fib(n-2) and fib(2*n-2) using the direct formula for fib(n)- as function of n, but I couldn't implement it , while the bruteforce solution was TL, anyway I'm gonna think a bit more about it, btw congrats for the victory, guys, you did a great job, also a great competiton for ACRush as always :) UdH-WiNGeR Re: How to improve my Algo. I got TL on test 4 [10] // Задача 1462. Золото дядюшки Скруджа 12 авг 2006 20:20 Hint: direct formula is hard to implement, but we can rewrite it using linear algebra like this: .....................................(0, 1)^(n-1) (fib(n), fib(n+1))=(1, 1)*(....) .....................................(1, 1) , so we can use integer arithmetics! Edited by author 12.08.2006 21:05 Edited by author 12.08.2006 21:05 Edited by author 12.08.2006 21:05 Edited by author 12.08.2006 21:06 Edited by author 12.08.2006 21:06 Edited by author 12.08.2006 21:06 VALERO Re: How to improve my Algo. I got TL on test 4 [9] // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 00:18 Who can you write me om email the algorithm or in what book i can find it? Thanks. adas@simnet.kiev.ua UdH-WiNGeR Re: How to improve my Algo. I got TL on test 4 [8] // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 14:37 Here is an explanation of the algorithm in Russian: http://algolist.manual.ru/maths/count_fast/fibonacci.php Edited by author 13.08.2006 14:37 Anton [SUrSU] Test data [7] // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 18:32 What is the answer fo this test? n = 7000 UdH-WiNGeR Re: Test data // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 20:23 81937319032993876558582070063011262115783024656965723338526424275071630557443673768160691777974344039339079218543821663526642065353277478431909789983160736348837929626796434540999450923786205450782143686270382692873692233405139629109704561270312322297501776980155782647708033073460077811847296059544586515736242655594916292010288630241998587835886957464588315061688674744586049802510938100726026534538639883653835446753146728656928193874140316597540202353213455487305219113003826047850156459479457447951648423579548704045234844929446845423587933723079796158760129023524040519672308404718221125336963212128205511547407802595672777585867901520427711491099757592076124797583476061864630025076181920889182653070760272884159824308542397653852400985696907858408387639956157978706489167805462854368911415071677899319871467455602850964575780531369593561207038707991166116257391616617990142018311285809472372949541001826651548109149596409807197380997932230498982610632747317000197354547509949735065278160290108373521163485352357077038417341404680343430978229222267611931184569548788576280109768575772879672619415599295926884517066063939649588253695834282602632479823971486742422068816044196848224503022646081677385555572595399717609483383203051148447238015528377198350218937442030369055848713320280710524550172256486540262008219704955151944469303730096667265538925353091481286313382299155890271045282453432557272252772046637042581378078908572780035752442042046549675078127 Anton [SUrSU] Re: Test data [5] // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 23:11 I know how to calc Fn in O(log n). But also i must use long arithmetic and TL in result. Give some hints please Sid Re: Test data [4] // Задача 1462. Золото дядюшки Скруджа 13 авг 2006 23:25 Just use java.math.BigInteger in Java.=) Todor Tsonkov Re: Test data [3] // Задача 1462. Золото дядюшки Скруджа 14 авг 2006 01:07 Yup, I used BigInteger but O(n) gave me TL, so does there exist a solution which doesn't use advanced maths techniques such as the described above, because I tried to use BigDecimal but it loses precision when trying to calculate directly Fib(n) Vasilevskiy Boris Re: Test data [2] // Задача 1462. Золото дядюшки Скруджа 14 авг 2006 14:35 It`s improbable task! While I use quick power raising of matrix, I still got tl Then I tried to calculate it lineary and got AC, c++ Petr Re: Test data [1] // Задача 1462. Золото дядюшки Скруджа 31 авг 2006 17:45 Hi Boris :) Here my sol: There is sequence a(i)=a(i-1)+a(i-2), a(1)=1,a(2)=3. Ans for this problem is a(n). I tried to calculate it O(n) and it taked ~ 17 sec in n=40000. Then I tried to calculate it o(logN) and it,of course, slower then O(n). Is there any special quick algo for long numbers?(sum or product) Edited by author 31.08.2006 17:50 Kaliningrad SU -J_A_MES-HeadLiner Re: Test data // Задача 1462. Золото дядюшки Скруджа 31 авг 2006 20:45 Of course there are fast algorithms for long multiplication. Try to find FFT or FHT. SPIRiT Your formula is incorrect! [6] // Задача 1462. Золото дядюшки Скруджа 14 сен 2006 18:48 The actual answer is fib(2*n-1)/fib(n-1). Just check the sample answer.... Todor Tsonkov Re: Your formula is incorrect! [5] // Задача 1462. Золото дядюшки Скруджа 14 сен 2006 23:59 Yup, but if you use some math knowledge you will find that the result is fib(n-1)+fib(n+1), during the competition as far as I got was the result you mentioned, but I think implementing it is improbable task, anyway can someone send accepted C++ solution to me at ttsonkov [at] gmail.com, I'd be very grateful, cos I implemented the algo with the matrix but I still get TL. Todor Tsonkov Re: Your formula is incorrect! // Задача 1462. Золото дядюшки Скруджа 15 сен 2006 18:21 Anyway, Java rulez!!! O(logn) got accepted in about 0.7s. ,yet it would be interesting to see some C++ solutions SPIRiT Re: Your formula is incorrect! [3] // Задача 1462. Золото дядюшки Скруджа 15 сен 2006 19:50 What do you mean result is fib(n-1)+fib(n+1)? For sample (n=3) fib(2)+fib(4)=2+5=7, but real answer is 4. Check that yourself Todor Tsonkov Re: Your formula is incorrect! [2] // Задача 1462. Золото дядюшки Скруджа 15 сен 2006 23:26 @spirit: It depends on how you get the Fibbonacci sequence if fib(1)=1, fib(2)=1, fib(3)=2 and etc. you get the desired result :) SPIRiT Oh I get it // Задача 1462. Золото дядюшки Скруджа 18 сен 2006 18:15 Well, then my formula is fib(n-2)+fib(n) 3a[3.141592..]Jlu No subject // Задача 1462. Золото дядюшки Скруджа 18 мар 2009 15:10 I use linear algo O(N) + long addition (10^18), but I got TL#4 :( Please help me. Search How to more optimize~Code here...Thank you!!! [1] // Задача 1462. Золото дядюшки Скруджа 25 сен 2008 01:10 #include <cstdio> #include <string> #include <memory> using namespace std; class BigInteger{ private: enum{MAXLENGTH=14900}; int m[MAXLENGTH]; int len; public: BigInteger(int n) { memset(m,0,sizeof(m)); len=0; if (n == 0) len++; while (n > 0) { m[len++] = n % 10; n = n / 10; } } BigInteger(void) { memset(m,0,sizeof(m)); len=1; } void print(void) { int temp = len-1; while(temp>=0) printf("%d",m[temp--]); } BigInteger operator+ (const BigInteger &a) { int i,carry = 0; BigInteger Temp(*this); if (a.len > Temp.len) Temp.len = a.len; for(i=0;i<Temp.len;i++) { Temp.m[i] += (a.m[i] + carry); carry = Temp.m[i] / 10; Temp.m[i] %= 10; } if (carry > 0) {Temp.m[i] = carry; Temp.len++;} return Temp; } int operator> (const BigInteger &a) { int i; if (len > a.len) return 1; if (len < a.len) return 0; for(i=len-1;(m[i] == a.m[i]) && (i>0);i--); if (m[i] > a.m[i]) return 1; return 0; } int operator== (const BigInteger &a) { int i; if (len != a.len) return 0; for(i = len-1;i>=0;i--) if (m[i] != a.m[i]) return 0; return 1; } }; int main() { int n; scanf("%d",&n); BigInteger r1;int i; BigInteger previous = -1; BigInteger result = 1; for (i = 0; i<n; i++) { BigInteger const sum = result + previous; previous = result; result = sum; if(i==n-3){ r1=result; } } (r1+result).print(); return 0; } Edited by author 25.09.2008 01:10 3a[3.141592..]Jlu Re: How to more optimize~Code here...Thank you!!! // Задача 1462. Золото дядюшки Скруджа 18 мар 2009 14:59 Use long ariphmetics on base 10^9 or 10^18, but not 10^1 :) Alexey How to make it fast? Is my formula correct? [2] // Задача 1462. Золото дядюшки Скруджа 23 авг 2006 19:59 I use Fib(n-1)+Fib(n+1). I can find Fib(n) in O(log n). But the long arithmetics makes my programm too slow. Help, please. Cybernetics Team Re: How to make it fast? Is my formula correct? [1] // Задача 1462. Золото дядюшки Скруджа 30 авг 2006 16:52 Read below some solutions. Your formula is correct, I used it too and recursevly computed the F[n]. I used long arithmetics in base 1.000.000 and it runs quick enough. Denis Koshman Re: How to make it fast? Is my formula correct? // Задача 1462. Золото дядюшки Скруджа 12 авг 2008 05:33 Better use long arithmetics base 2^P, and then fetch decimal answer by sequential divisions by 1'000'000 or something like that. Alexey How many digits are there in the output if N=70000? (-) [4] // Задача 1462. Золото дядюшки Скруджа 21 авг 2006 17:23 Cybernetics Team Re: How many digits are there in the output if N=70000? (-) [1] // Задача 1462. Золото дядюшки Скруджа 21 авг 2006 19:17 14630 digits Alexey Thanks // Задача 1462. Золото дядюшки Скруджа 22 авг 2006 15:56 10x Abid Re: How many digits are there in the output if N=70000? (-) [1] // Задача 1462. Золото дядюшки Скруджа 7 фев 2007 12:49 2072801145996145261520530447408850863428513339377208014386060985843763728990950560338251079604581881 2761764843963097882756899306880632339149624457792521065549662450746982954629516070098764978344151183 5995330030762779087743459391817243909019805275976633115556130331941538448665875113367934989079027834 0569811790271945906685562735304733743410753082978063360291190842638975525282371376255146251390737707 7479794770248229483843646633681833549215123470585482715472809087383941758904346522640847918233307726 9328866108345114427090779695990005117224442643471755382945481853638762026546985115627193770965426310 5394352702808301103424957405054432898553516895529167136603624447915874323780327952040118805325278847 0288847800035137267512317663342926011439333402801452136904199295820198703432837127533865033077917441 0100898022841492469103704073386054730663565822108884580528522055691701523568506284269126884159083365 2981898449962724562358921065055713479149834483505479477562321118755467916998143411260891457484332466 8332643775010924705690019102274575145613483922681596385654759233269444264241619526680808134173728034 9475872783233388450598439414037223575558750012302913355794850648784308559343577303219076693667107597 3043115850209464408267038946442563894220187739318055364751537731743362821609888945133271851672020727 6058883659104584529812229076091130643430114436305262385420314059450210042195431947096493318081320875 {AESC USU} Evgeny Kurpilyanskij Re: How many digits are there in the output if N=70000? (-) // Задача 1462. Золото дядюшки Скруджа 23 май 2007 19:36 You are wrong. My AC program write answer with length equal 14630 1364009824826097138409874727232071592670236676434661436958625067025953048160195316590256042336050799 9240285236943998597755517864435051077996983326191535648244715055632646494475836054016954249495840368 9429773910248895618431459625704116289808535035391530034504604812315114781580074061315294350832017537 0075316588558621037290575768717973347211695376764733809184842518679512635211464818187929679448162171 4120419822770736842403909341535418889602295980606749453924444722749831991886615203317279082083644209 5859240299070567565865919703493001702802472903786299155673454789689666667376454899780585080004575093 5051125493829019415429695413340276560732927987519009397229769042454790699842227702861077089955276947 9789770809912699679036724558045302233243433525289535479438177687342796156957246446368380611154909281 6665987538395900320557483881627165663456662023298993638270329837346030637435609378930404319693647318 4274082208688005546933308582126396393570316371577788830439436603431287097669304618549789750523184626 7843458797169779028687276836220221960836792717802396441522167092797575419302668781994602478047954820 7111309485485585550435098771564087074395039589491138377171373923232335139242441300741769871281480225 5267992730393849273766037282436366769244644903354247348031793918916925525170261756771301579919588498 6808871345915274357951778682894552000177957149163658756462811490948886407938914939312007069050398406 0421014745929272424162538821255370862468542073842047594022889913407747209817012628292481948963363330 7939963131447386415257485572643408327509651957092250243103948348684392532233017316238952357998543982 4057861152358071479241442129355144981213727649154029298159415108878561191444503956490933543989366275 5476693451697124796986538652803013927470184228427580423342479901925125866426725877450393637258195572 1782473382063463161774045734526941702750374227341652617262720962224857754824110140484087312588163804 1523106427697333354672612448176456083478158539373745895550830825347048861682117082560549456732885088 1475631562039626298178595519201730677948436638233523881391210054827979055397139993817208120168116329 6288460070939733609052610605369663311534142998014501961364922332451195969754974592326823166645888680 4403375572707080615763420908194846530357011423477253675543144101045862936136284454801994422499190884 3352857347314949566845314778019395838857178333322239854715575929264129350835917679297089013897116627 4372139408802137514854636173856913161907263195099713368193915945451886436667408952618596780693242314 9237949772877498224294687623996392825690487930236479755728861918888984853415400062679899766320426665 8293295720878995708137096178225000230194120785113009112645549222211944085524290385767050610240047931 6545314437357481779006695723877820808102230715081374907274591463211612068386773592703872609861628510 5379076634740892414609423967932938037002683870758184054013121277862930507883202728039728695223629671 4405082543184635363190348392402776477523040115490760991228640888197449032636381189271074381795272568 9075324877656376547197765262487229946969358669918789269768988475499001497936657392316599036478131133 3204013854844314302474841069002711460385258509137036292475892192130879747620835074624337477403435211 8415619303701159869206422077086409107904032024714523285368272053265861848465230070520861494099480226 7435786255747368365306838920309756635377795033127881075980085620812176050957930142548915534279463009 4750145391183414042483396408688734779431919318194978349568737346936347781290732895276218516210946726 7436337611871250439748821173120093547618262606042826909163975139674234623923221614719799877520732154 3066704622475106356778963697494186051105605304812664829091352186057357857916633482001520888268141532 4360409399684225241226882309693402750254347694235362673598159773362672314888685158048634887734300016 1729746836570483821312408198002932218253455291051401328786389248080141512715347936741763463995963906 2963788498476188649195763089217861449974843488472364792259012642987431809805020908025114464942078267 5593078214744594337511451362130889682542356307894322486914240186338707824160946534562311569434534628 8428158430385792502340410452051555799292903326762212789646589977578101610481254672046000749929921508 3125471374682076568544067373897549128421047744754378216972051595358526866654862264182730369096329809 5062047596436253209696438044216889665399945449403222479462737261499580811627988298506722619278252207 0063250095759319342238580381927454926995845465289348673223104199502512000826182099837706931216243921 1340613974567940610301373683539706653704016641501664968212551793736859463693068625087567918666501708 0610414589742635794322688487683787396710857574031398044126011740903145162747929156747553693372145713 9618690162041054285214050232013350171241895240238969646303658404283950989614825646583806078047272611 4689972755096312127885566203846847814386467979251167551069894299187930373541452124626325756146098649 2405437184307120591765783483550686236709296325841204284403813473705036416713470811227925965077581461 9297576891750969285314734979678078191753255653263837413037102976173721576441284595471527500362368276 6876773816031484466757826047430047078252405830038624516477450897620164643753005333066054319219177538 0541078845618401316851550615619430270974579529093102407764335636130589686033962158194896518572857875 2824420649761504946291500742055847046544056824088681981271562195806156354409970664408014059011873592 8395188643481320881531167270961407656882577854077825454760597098721934349265246149504706136343379823 4727113718768765905794755395682321867323095640861858910833291040462746329059258505641320043856252256 9835599762320000779155274241387687656306858498235035683431775514535495409514154934954415670092483709 3710043493870378107090821390259821485948960638134531060985160996270892503459690196742012575466528420 0063363272026613848029694309114722629109656294132368053594878145445505457158647837758089591843386321 5107121702641767417509735803668041150207033014809447071833158159713712811151845637826827707954913612 8512913298527906965463275404749417753209435580584236922971946209217948017516657525469727656530636739 5886972033821785163271455943158878624901313017360327713300305732099898895420937277580427389981860308 6273557191837377757227543315168126385925988164999800570074186908320101668237274492263531944582226504 6066940566982296323251235401737580793753639671956467405302142903314991574110728239688292299819851468 9549990439175417167887213063006835331826201566281485015669864409645972894131730155063820988621559783 7013371249222199035919220624604092098648232693897997526085113589237014087550077632643875470371249574 5644747967873427442094378730929407665307329139484972510326023112669695430839301954113624270144119847 7977681483321284474717198027500035671557714685659786646866081572342587559384352886120011260516039926 7687071754381973142481785505894160179153044257684332277780069430553422655328844212346365153597830693 7884395235853227059767973136746067741620075134993307728386243479203461649703365389557284978962621780 9888713259977613649746910094308797813453997531365198803022329655343927202782064530068528263766360076 3684541844788494515143657677779925502137895660295908030398572270084597901147875002703803207882228095 2264513210925204333611979710285233801566389133397201620500332144153735033676172234355818886703096242 8287611671823905466448155322451044228029827813403817322502381553895304264537449447910774606117315708 4718857321580091607327504002945616685326403282000445899731835403957627041538107813429776480144115238 8967795056663576648202829572876080436178261996205471787813739076866124403731011007204085680411451880 8263626278556480834141648465252407641218595353663141093771159362278685001090429932837630737655601970 7440137189338087408571040354672026254595032608941127769062879878207257197050658871579896240160006676 8709468311707276630960214823092102439077822676299834089059576329360735247241917097113275904434642611 6266352779839261609229191394071749103093608421173134860785588761273089527187626086447050503686956715 6081096746632612726359945335387293535403908622115928891483000694323725521063197374664146132139423678 0509355304492345645516486783449532763865041450368693752917417871927035268726889219603766697231243824 0363122407021118620217243379465112814664931004242386344744154303241023372804989938830501585462838269 7889552215797796931033500803812048857567855984802618282301162190719496767754679849007514884547306560 7259627287768141591588803096103433054153978027738758514244033614859885996924914553182584735519223398 2712832009897168298969139872941150522644657003149466032024060810916261639298470376356465425761773354 7418010926615927984234453604631023144041617140752273086352045348858075513244188932025630096701606687 8778435717163806586808652231088632699955439647645553164237708288801854674761122009996709235713252234 8622391856865314111970600509258475737511491667829170387729515074051080686948812439748651727120562343 8600803528068709567967448218832620726956941834767967725148844785536407127765938615854029810074975034 3297306362706992011782267011387882996054886007298929940341015174104975393261122433159398525698569788 8687436968951608203034977880095740733502386870843619257973722112109190755470395418033838409492754491 8004972712791710968451944244355281821841353463940849018900740817061266403907420038714112829649521902 5803274684741895723885734632382138581544848362275309357552249676539263464645888115712435057489713969 0284548038404131312799005087552961806023660197527233756758232652904529766471925635198804541910114776 9783690805617030481583378400456314730307551099367030603779416751468310560556530644603573991513839770 0512488942084764788549183625502572887774512429905535868105397845282866439642509316173465499035073432 1094231997642091468944080288460015223091040555046088400550350773425797257798381831026286089463824286 9299273248132970987224705512221789103108020060054201971564808813680129516785223127782660763550760132 8559813546639567586673495107874356266005013996528004492183000333280131036294882579110032017501182965 3770958085791851511171736610268795407110902339843697166983622981632102013486609511485745600600969838 9938047042270514275620798351721271909270553475051334889655115480433538309526716685635233834631217781 7957639405093821465781933238146823845867578803556927211183394122100681863184876384882454323051767191 0698349813046101152223301310614901437069818800828760002518814874956873276106939655669917680489369613 6635518420598679633000017887490810805514544766291237473238459061919827806560698119597951591725698251 6422568934363716440106878162003770671834713654734338324177188046470650369569954286441531519025677458 1389486710442031907429792196969832929487336922138377250510030682362172472648480154963987985441999253 5059046320109952082416708112512567940919177168714458235478450035661019765682437671637327685840281519 8372820988832897053424996612800919790006964093339512937158488217946019097528597089469371652466365174 3309009994777075224239622737913167999659888360490457871912356215615245253612843243404983626241578359 2327620967267142491961435833516179224118362108953831990405990031780570674092731481988264797732066052 1793233502336711052278724638893211369539474512171979119533289956710701856789227760026277685590029925 2483388581923131544016740307947197290115945374672570943751430851320887057983268482851591757807642838 4476413806005253787145074904558032606054695168221891429875988115655041207700101369712851225361798330 2072697906859090352638316733701682480488581824446923045301862513599158258416567892412936736631764003 3971859141442250383090181496898600224754802481929739081777567352066404114056928381500169969743948492 6770934879753809579366597105134979950187224407195920697730575423358373278360223437603821366982679814 8684096309424657999701767984122959206435577299129712886544460676562922664780739502447731027261738459 4783584515677103150745313912141174003272979334339976958912282667575226520580486282894659505954722345 2145497176084629520790274714907335584418701251717346140471073255914903896366370560249110028383587410 5689874911571411407195839999960302694524864354954910870537440928726054083213482380257306012324392126 5135564486736512376830604787697713657669102121764632612244452254494743074981517209939278017444132388 7884000444960977727254098842888748797260712479106089194531115353034825819457511783769626025789449450 0856828126635711132660038839408789829330057093552848643489474052620082937605152238526995113865299530 7283038069810940100589472382469770214314879660079977578998941320020718983413950955385218107734322448 9929840917289599508725779971673312443193265552771413613308291771949785133318581422911901245132117301 2376675643886706827888462486811878931209928820982114665430431112345064662166990619714114884803027273 0441313478438684963133953337425191868408013992346375211393540171128272604624180114350723544864794135 2322331002688267935284603051941964555094166212650129742151198083533145585860047354050980736271938316 4965278803513095854206785094886941306402496728270036831954110884990384878530088701541394336110869116 6586994893446871585572909452503844568122351967851965161368968976584184505901979485353917262154288767 4065977681390138098411145708252130535551391693408155028557012386916925839340839232406261665332033498 1971012012407227612237324685261376775327550460751784209648093598816488508817175494867606301099267318 8214114621053769600416142885595332581151762998398231566420668873935846600276346869527977864790063852 9735092858909404238764447914874567495372196602183177817790161234314200098724707634477504608051975546 2699561480816120357060309292893102822593637734707203792814192646707315491428070573361865591853511983 6589068155185042982867353118647446500763832635409335988591961982319767831122559500659616259276465607 3141773622275265463370135394576372287612432377634934495540282402327464070562231942199656965475481977 1162586435516228986403291661983619828978312363001895392975604714452120238232552992864767246774475394 2913367642537112922382465868765830243223480186507726443814432694034578574324786451629071723245488129 4353112243551324517260089077727674479983278658336154625457720981696540670665528178833570635655681298 1330919601539362688738079414212978695538663272508153007207303812882214328587391487769201510563749452 0900573840320512634149997591961345554687874230740166548852791233139298313404128605820368651518625658 8810652952676401973188772536496377676535754671148746301645859575320914901033012788201139477819650024 1493574224008823555824663541639323982500024724974619422821107032679079238129469074783622772447564421 0140370675263534155544266070818807822602135897840220998786574507877939665444757459302334027296817191 4683677640077995437590798828127 Edited by author 23.05.2007 19:43 Edited by author 23.05.2007 19:45 SPIRiT WHY WA at test 4 [3] // Задача 1462. Золото дядюшки Скруджа 19 сен 2006 19:02 I use this formula: f(N)+f(n-2) where F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2). But wa. What is in the test 4. I checked the answer for N=7000 at the forum and it matches the answer that my program gives. Can anybody give me a test for 4. SPIRiT This problem does not need log(N) methods [2] // Задача 1462. Золото дядюшки Скруджа 25 сен 2006 12:39 We can state that f(21)=4181*f(1)+6765*f(2), f(22)=6765*f(1)+10946*f(2). Wherefore we can calculate f(i),f(i+1) with N/20 operations. All we need is addition of two long numbers (I used base 10000 for them) and multiplication of long number and simple one, that's all. The usage of recursion formula f(2n)=f^2(n)+f^(n+1) (or something like that) is overridden here by the cost of multiplication of two long numbers. Todor Tsonkov Re: This problem does not need log(N) methods [1] // Задача 1462. Золото дядюшки Скруджа 25 сен 2006 14:07 @Spirit: If you want to I can give you my accepted Java source, please give me your mail, but I'm interested in any accepted C++ solutions, please send to tabledott@gmail.com, cause all my C++ efforts were unsucessful, btw I used base 10^9 and I was losing accuracy :) Olly Re: This problem does not need log(N) methods // Задача 1462. Золото дядюшки Скруджа 25 фев 2007 17:04 I'll send you my C++ solution. I made it in O(n) with only + in long arithmetics, but it's well optimized. If anybode else is interested in my solution mail to me alutsenko[at]bk[dot]ru Cybernetics Team Recursion [2] // Задача 1462. Золото дядюшки Скруджа 21 авг 2006 19:38 Today I solved this problem using some nice (and easy to find) formulas for computing F[n]: F[2n] = F[n]*(F[n-1] + F[n+1]) and F[2n-1] = F^2[n-1] + F^2[n] with these you cand recursevly compute F[n] fast enough (~0.25 sec). I also precalculated a table with first 2000 Fibonacci and when the recursion dropped below 2000 it returned the computed value. I see some nice times on the best AC list. Will you please tell us how you did it? What formulas, optimizations... Thank you Kaliningrad SU -J_A_MES-HeadLiner Re: Recursion // Задача 1462. Золото дядюшки Скруджа 22 авг 2006 01:32 Where can I find fast(n*log(n))long multiplication in acceptable form? SPIRiT Re: Recursion // Задача 1462. Золото дядюшки Скруджа 18 сен 2006 18:33 From what index do you start? F(0)=1 and F(1)=1 or not? Cause I have such formulas: F(2n+1)=F(N)*(F(n-1)+F(n+1)); F(2n)=F^2(N)+F^(N-1)
|