why taking the biggiest fraction of remain assure that the church gets the minimized? Please, anybody explain! Im also interested in answer! RUS можно разобрать на первом примере. 1/2, 1/3 1 - (1/2) - (1/3) = (1/6) Пусть следующий элемент в массиве будут равен x. Тогда доля для церкви будет составлять (1/6)- x . Пусть оно будет равно y Следует: x + y = (1/6) Тогда для минимизации y, нужно максимизировать x. Also wondering... anyone can prove it? #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<cmath> using namespace std; vector<long long > C(20000,0); void mult(vector<long long> A,vector<long long> B) { int d=0; for(int i=0;i<300;i++) { for(int j=0;j<300;j++) { C[i+j]+=B[i]*A[j]; C[i+j+1]=C[i+j+1]+C[i+j]/100000000; C[i+j]=C[i+j]%100000000; } } C[0]++; for(int i=0;i<6000;i++) { C[i+1]=C[i+1]+C[i]/100000000; C[i]=C[i]%100000000; } } vector<long long> D(20000,0); void mult1(vector<long long> A,vector<long long> B) { int d=0; for(int i=0;i<300;i++) { for(int j=0;j<300;j++) { D[i+j]+=B[i]*A[j]; D[i+j+1]=D[i+j+1]+D[i+j]/100000000; D[i+j]=D[i+j]%100000000; } } for(int i=0;i<6000;i++) { D[i+1]=D[i+1]+D[i]/100000000; D[i]=D[i]%100000000; } } void write(vector<long long> A) { bool f=false; for(int i=9999;i>=0;i--) { if(A[i]!=0) f=true; if(f) cout<<A[i]; } cout<<"\n"; } int main() { #ifdef _DEBUG freopen("input.txt","rt",stdin); freopen("output.txt","wt",stdout); #endif int n; cin>>n;
vector<long long> A(10000,0); vector<long long> B(10000,0); A[0]=1; B[0]=1; for(int i=0;i<n;i++) { mult(A,B); mult1(A,B); for(int i=0;i<4000;i++) { B[i]=D[i]; } for(int i=0;i<4000;i++) { A[i]=C[i]; } for(int i=0;i<4000;i++) { C[i]=0; D[i]=0; } write(A); } } Вот код, скорее всего он не пройдет макс тест, но при запуске на первом тесте он выдает мне в студии ответ правильный, а тут нет Потому что первый тест не совпадает с примером. Попробуйте отправить программу, которая выводит "2\n3\n" и вы убедитесь. ну у тебя и решение.... все ведь должно быть гораздо проще, хотя я тоже первый тест не могу пройти #include <stdio.h> long long int l; int m(int i) { int res; if (i == 0) { l = 2; return 2; } res = l + 1; l *= res; return res; } int main() { int n, i, k; scanf("%d", &n); for (i = 0; i < n; i++) printf("%d\n", m(i)); return 0; } По приколу, я сдал задачу. [code deleted] Edited by moderator 08.04.2020 21:07 WA#1 у меня потому, что я проверял, действительно ли первый тест -- это N=2 Я думаю, что здесь всего 1 тест сразу для случая, когда N=18. Лично я начал считать максимальные значения на калькуляторе и пришёл к одной закономерности. I think that there is only one test right here for the case when N = 18. Personally, I started to count the maximum values on the calculator and came to regularity. Very short,AC in 0.484s. Not so fast as I expected. C/C++ Karatsuba gives 0.015s!!! Why first test isn't like in sample? I checked there are only 1 test, and it is "18". Where another 17 tests have gone? N=input() ans=2 print ans for i in range(0,N): ans=(ans-1)*ans+1 print ans It returns correct answer on my PC,but gets WA when submitted. Well, there is only one test in check system. And it is: 18 I don't know why first test isn't "2". I know how to solve this problem,but I want to use the BigInteger of Java,could someone help me deal with it? email : ysymyth@gmail.com What kind of help do you need? BigIntegers' usage is very simple, I think. Just remember they are immutable, so if you need something like a += b use a = a.add(b) and not just a.add(b). could you send me a sample of using java bignumber? I'm new to java. Edited by author 20.10.2009 21:50 why this is not correct? #include<iostream> using namespace std; int main() { int n; cin>>n; if(n==1){ cout<<2; return 0; } for(int i = 1; i < n; i++) cout<<(1<<i)<<endl; cout<<3*(1<<n-2); return 0; } for 17 101947476276204101728256649522401828167927212018620660601704890929001825509713\ 523503992610358334066272592383395838866387684206587940612931467354271617915520\ 937995552021084248226726638101995425579805732299965812369024137733196293515624\ 424016917925247649882464052696187736119522132640993696042743480414771264544528\ 304342996477011745452606136325735302189423673044792743354919189308823448247968\ 364421235334689505731269305763052451307463747806343113812624926109241630690221\ 319433572220844418278565182710065248974135752363837484684227814042631918627155\ 461779101734021597624242710578359837429955380225996920358684927211301458328724\ 872971117350243844049604206441001676118134664338476015421798968307893538522879\ 738221475097682927759727395878448090218721802381455630439305830088798521845679\ 481860616779484116388947412631032214162894648924320167381731382043760565596316\ 369583724745469072297566662773233839980675859313837171769862327336088652054094\ 267810251588071940758900455743286020948251380733842671672740944609550580767140\ 732173862408107529498531326164067492981649810743591794028985785355587051520395\ 534630526455902456336065991163514533196314608519640788565818155174136944051021\ 402419912329933809924219549508467344366233051463150285255689476642468105302211\ 129811175620821751513860525253757739561042423044403448246267339558656517317865\ 002657449204595579742675299432398952884881848630853237246246329746536660490193\ 464231004280212833182760067389817797704719330912736030371597912626318279787464\ 408039560242064494924683367742401523278572128169942111951355492148915513062977\ 767559605391394475240035421689924596879829323560599623881796417132645355452834\ 213394295243124161077956028677251502132801495011896740549214977611725577583592\ 694131902274214479285847997219514083715777380237852141555799465598015245152196\ 197540850796658589527188879862044709016545796583701795889195497514304242690490\ 020048282090997220570151819282983750070905128662528860703021805696428045708735\ 217070342408403948629748287182302572655831689847248362835661078053350461256021\ 547252746204855622282300021449560142568349748618704900105957291367569310068046\ 468168740774195170563917695384082803306556375506007071106140974657491081051319\ 628733980823861151213743575371668595999162366202372771193718906231527267750197\ 486208221400172590739690964186859083713098418413904193544036347981505565030074\ 358430960182277688743565437791001750095814547355349908834277382701916967194842\ 245938118072198823848678058047817857919108391286687178444965713477577691631264\ 683265079619859936065323962869265275426820111891855142296804948531343541948140\ 233325861685585654210886918693438429463852147233236461744139070486591334508296\ 457638112829900981331742227600028166778501177206627837766424230432751776092660\ 905333207273480471338084952622102287953496875636006963328797863179813674926308\ 972179356464333251094493151732499958616350679087178949479216828756235540404960\ 713180088292868461069552267966556582868379454800273376303872247435830687267393\ 790632637291832475998713420228193860684332834272020209787394749585310693327423\ 238069146069235258021192858102358746511372078580637116458067121739895510040929\ 701669398478973873849065653363239219214902435330524238782375642808353026188773\ 975983490697280154677778905491647471081200979748252065741117416477107374679345\ 743129808520178057105601496774507566188669824677145600348843302843159620546174\ 334832342261955415164552484365573829013677168443541042252294869025362302975188\ 357843863352803540278804875258862826997522470901969159918254181349566887374862\ 780691547981769474082634729847029564231178299643587820218295909268066469439209\ 361491238062665635552348001777523991902386442621767153531136625588050180493206\ 062242422931907554959039295465983742398584740169266919842721984484510373349152\ 245952678807152410758717023226165898261554089953972142911218163641942164495520\ 363355981591449370142813000605247823024169443289315723858776805353395074747315\ 965280001341580608595769985570739736089162750132694522089916488924640668733155\ 223160937927062251627103706892028018658869521523347072156904472183243404821906\ 304272096715336825846963200847460589163253872114645787381529273086086455786566\ 275126829436164942555105137673574243094665153514651721735923240573324863824143\ 359851248308716379355679879591213016511440586376295006227271629274118951942116\ 109405534002079180597499184909932263968054958258105257514955012091459820800057\ 750331964913568287731523210748968398312957273480719457275559998248560139266250\ 842179935854173511566613222948421881382475426284893241966842479917946517496740\ 184005176543418886207284298477461122754701546519893184842702869621306705911094\ 049863539818995805682571658767661717581202478037805775168469748014496159567653\ 867547996292165520326070898580254978876493271964884556400923688543210364055051\ 615791042268351757817686013185351170250274124497224412719348764846625708068905\ 347316664552317520539285800977782965249223808291145291897524324064574143276004\ 109309312489603647534696923445636909725936822586274552277423207555843177718296\ 952141969023679154209897246157142828813380353736229450306049855932736418036398\ 961065760057909708160303588848920437271046591207676445275229419800540502365601\ 287894038341619051056594181736631833907096742273385627262684929705142348821715\ 717757958905859254479917848700048385072249130142420650970420023287836827630391\ 269918643914897622117657803662758429145580464113366704590130560966336742522948\ 426614878287442493127007876368649283731064173754397064710293902186485691882881\ 716468262176381143462572160900086704950634329551688625081703810335385515304188\ 304427279243385438689682372007527042313863650071970451630047737592261712679997\ 032408347081035265513334702499006133711987239421535054848463109822318586991438\ 551922502617715683296404173690528506176471786187891982050545166477348649137207\ 858429882060978569493345683444105018762245149581702579220458862325192666588097\ 882057919708196676295001981428692007892030715958615319031669962717200873646950\ 008362407507959942578561644410507683474807389207851292100875691409227155727299\ 364582623223275295062939276067857778361135380509202853919256414424503014505002\ 381304252092914928928657140629156647824122226663231270929114949838133512858284\ 553659329483020863495070396992270655333530795534599510106923678406707717858463\ 733321785627940852507792509130884345783566091608572106334515971552960334058748\ 839064383371028242595100897586460484856407787378736322494137454900025766401953\ 432343390997934836648888471475774056788466362851920363702646297700862884419541\ 987571882177506168821922809933537205416312245942012156034442836293522503739936\ 065901336541052522501549407560959605649286737153302742922152520560377209508086\ 113982015028412372790811903863008802363619805248367847394429412199369638423963\ 346257500612817015824336492312600977669312112774203566434781934594072293770110\ 076734956699178075515846558405491752217839681661596291831016443991991412071772\ 137912039918597306162686225588910504498519604052700515641172600244195414239780\ 360630322446478496281792974758878314317259627986710759191054660959328452748938\ 311478199535939071913360744286895873622646699721551825987559522917879477445778\ 382908124421543471646833635556615676388512579824507455359252651958896902958855\ 668692843421836979526955093577635147345988824158949081202382108767126209821958\ 442260208948449410343769646095764053362538731014265928873692318388291223942552\ 421374501833810037541831933487375710124093270523976456909327768504943218645340\ 607609285579343097200825103534646400864178642528922574211254451904465997353464\ 510210512105006920359247962529839263726973406559916187064671120861970908188292\ 868899774538386530986348457725714314783858497404840192981602404268584138070725\ 841997724622331835018556950009953063992884998005153946253938533541281660071091\ 429424514187229202508780169660518187519401276672888317734775745997919858219524\ 239671755968351481290456477508563245546726259397317514968395897774994941937641\ 857833929270815117032962881367672472733333474420273123621265406470085013468333\ 119658823407066792641139759838451752805070829259243717167818624584861840639371\ 799738640140902077418451591486238742100062761371526700751326999370092318078314\ 368489806490770522093379075525353121672988587838215010713807872451131794229812\ 571740806401522059317899185264121384303947536112199986762810620846685091274271\ 916661463411839224984962435729012932133343175807034982705801566084727334333517\ 750351634518081659225254828123214035942931842340124701666219235091380967050219\ 134380278144223506076120089021003305258960092049465404548159621409475037953312\ 173078114622050941210429800533486071767071202411442403056916088204245448279934\ 704578107634786938798517235147720543138315118953409306950329781338209463889377\ 470710968341797194581860416354750881171100231404610379962003554616111671902862\ 697124103504073629731011619138818833069834499687213768467359661901421300332751\ 135267231414560709815668898412329407691576395889529755528790383487960697775451\ 764038654169029787737935618427828193963614002421796514377717795463593318199322\ 955753836683147459314864427699947923397123162519743718033336537904778738909605\ 637535529913079411797144286416514371413616596779207789988278478924015088300574\ 620331274640498180855093038975080909740589748091444091955495089168886894992931\ 722766013965335478296019734869490910635590720643080340322002266437052736851404\ 370448578218773247775710274843449000512256418836859647205346520886692955706538\ 390045352933459827863586330492444094263842446831131327801920868587368676765127\ 464799206582996201527957193631845220731936291769995842530852430364383423166599\ 679992975649367769381074666316737598564092830628272038204585425201246620334489\ 400821894768076677303753945731268505937331250013826162664602013860213628505438\ 613088614606018479330817153878987155118618609687453530431653387882068520150477\ 956100336516235868097480522775325784653682625830314869032172517939835171315827\ 527818656693744191724828177518601488616783147760717381768688995404385410128790\ 806080374638954228188788965293885694114845059354594141324091298839591528017533\ 374376909034613941653796919310036371349410974127680808733282647443187903534964\ 642131308935682424358670417681693542973321116904594079146133429407276088733945\ 898033202097039338159676498549164777673752492328509349038688744456934749959878\ 258115431677204583992640922080230035273300812851769756693954561073535941385671\ 779980272011075384337721741933458261162553735568314260381570179840749330416564\ 616138089504727323977641731169447353392419772273507504583381222900280346430609\ 668801170796983251907041738862982742733739119007927215655537267575350108342329\ 731081927263234354309447041595207150072369177349725163439778171878237027628984\ 333053910381856127025724485995310690236572281053312911768824281104255667731327\ 736458715008245966424251295625486976554262285167088557534827179182711225022332\ 845222610193710107652038966100641295486691349710311830287284272469727839643508\ 946955974388642039006053186406508749446240835991794524254394068907649064544452\ 350242828197100347491166053166607446120481569385325342398012306741905199958390\ 128295206683964040549289874988771568591787120902315278985275898941333362328422\ 266369156347284504772554552506206951479068139196600874413295479414473418725240\ 107208106596031566745371724243015265899349651563027222546179832138183186377082\ 715966183438825270051206480864418998224084738692973627100636535354403693980897\ 627795927225862076213309855053657925340504647080855990490604097983768359676020\ 237508751128068071367571958957906787792366376078741525473958355866250698725299\ 401727299234522457850902882394018752173543794479867862490304338035339553949480\ 533652250079630747366148838542635928380062014110986183591526646807726525104184\ 827063578382720829337894312562609400025648517428941403830758729200703182792813\ 354385027899116087085610304706934512867480416613355379821893749723434880657907\ 554203214056693702832236842657009096050756966707760262570104538244439768550998\ 803621573944751131417524487370379997581423292608026951132955215726736195305524\ 500008028004278241580124445172672845856833559303763883412738078735403012875435\ 196438724201435550629314003242865871060459174526037526146069010986769814990479\ 943640765942659527630905623713437127333041857359589077454949500166841617658178\ 497257881864153377674716536605247720987938913725824327968170828620767315494360\ 803994257127167979564613665895891374659799355444426493030394805401402462310282\ 893819382701745421701555881725229367682313142125324323315200674528018932739836\ 808896328648138573883303088450220616118017085196397999206172414294846638520478\ 439013164544032387576566903465885352798453222311399382356831803583763409801338\ 783777117184879285557880853209634110451074793500334384861799435547383606869245\ 365875167216703128980893926597268388841854917396424738722231710181510123192620\ 547842731837553604377204489437125790621726819914691642640604036927915509764408\ 638948576290607782570194036590190058645888660696214150709897480692517189975771\ 382406186742388147227908175336823422378979858400616087580384418863441649637944\ 184584180656828304016631806032427311596287322544908429516198672707778430371394\ 990050485057523131032041168620610716240871714017424485591690725187211238174477\ 830719311581218217414248803834188552501147223451149926063565937553975663259909\ 054515083809899259881445992853611185649260234526169552619316248945216272787187\ 821466608617856311968660449514151206062953427830249813010159032237499601291295\ 807 THere are not enough space on the A4sheet of paper ))))))))))))))))))))))))))) Edited by author 11.07.2007 15:28 I have exactly the same answer for n = 17. But stil wa. Is the answer for n = 18 begins from 103932879... and ends with ...884485443, having 26681 digits? Edited by author 30.08.2008 12:35 /....bigint class...//// .................... bigint a,b,c,temp; a = 2; b = 3; c = a*b; if(n == 1) { cout << '2'; return 0; } cout << "2\n3\n"; for(int i = 3; i <= n; i++) { temp = a*b; c = temp + 1; cout << c << endl; a = c; b = temp; } ................................ //////////////////////////////// ubig ubig :: operator * (ubig p) { if (min (n, p.n) < 100) return simple_mul (p); else return karatsuba_mul (p); } ubig ubig :: simple_mul (ubig p) { int i, j; ubig s; for (i = 0; i < n; ++ i) { ubig row; for (j = 0; j < a[i]; ++ j) row = row + p; row = row << i; s = s + row; } while (s.a.size () > 1 && s.a.back () == 0) s.a.pop_back (); s.n = s.a.size (); return s; } ubig ubig :: karatsuba_mul (ubig p) { int k = max (n, p.n) / 2; ubig a = (*this).last (k); ubig b = (*this) >> k; ubig c = p.last (k); ubig d = p >> k;
ubig ac = a * c; ubig bd = b * d; ubig abcd = (a + b) * (c + d);
ubig res = ((abcd - ac - bd) << k) + (bd << 2 * k) + ac; return res; } I get TL1. I dont understand :-(. My wrong is big constant in simple mul. Now I get AC! :-) 0.031 sec and got ACCEPTED I got AC within 0.14s...but how to get AC in such a short time? ......maybe I can const... ft.... What a problem??? I got AC in 0.001 ;) If input 1,what will be output? My program beats the time limit without any hardcoding at all. I am sure there are several other people who have done the same. > All you know about long arifmetics, but it can be FAST also.. > This is a problem that I kept untouched for a veeeeery long time. Feels good now. As far as I remember the author solution used long arithmetics with base 10000 and it worked fine. Can anyone tell me what is wrong with this program? I get WA. I used bignums, but instead of representing the numbers in base 10, i did it in base 1000. I checked all my answers with my slow program (which got TLE) and they seem to be right. Here's the code: type bignum=array[0..35000] of longint; var a,b:bignum; n,i,j:longint; procedure subs(var x,y:bignum); var i:longint; begin for i:=x[0] downto 1 do if i<=y[0] then begin x[i]:=x[i]-y[i]; if x[i]<0 then begin dec(x[i+1]); x[i]:=x[i]+1000; end; end; while x[x[0]]=0 do dec(x[0]); end; procedure square(a:bignum; var b:bignum); var i,j:longint; begin fillchar(b,sizeof(b),0); b[0]:=2*a[0]; for i:=1 to a[0] do for j:=1 to a[0] do b[i+j-1]:=b[i+j-1]+a[i]*a[j]; for i:=1 to b[0]-1 do if b[i]>999 then begin b[i+1]:=b[i+1]+b[i] div 1000; b[i]:=b[i] mod 1000; end; if b[b[0]]=0 then dec(b[0]); end; begin readln(n); fillchar(a,sizeof(a),0); a[0]:=1; a[1]:=2; writeln('2'); for i:=2 to n do begin square(a,b); subs(b,a); inc(b[1]); k:=1; while b[k]>999 do begin b[k]:=b[k] mod 1000; inc(k); inc(b[k]); end; if k>b[0] then inc(b[0]); a:=b; for j:=a[0] downto 1 do begin if (j<>a[0]) and (a[j]<100) then write('0'); if (j<>a[0]) and (a[j]<10) then write('0'); write(a[j]); end; writeln; end; end. const max=30000; type arr=array[1..max] of longint; var c,a,b:arr; i,j,n,k,l,t:longint; procedure chen; var i,j,k:longint; begin i:=max;k:=max; while a[i]=0 do dec(i); while b[k]=0 do dec(k); l:=i+k; repeat j:=0; repeat inc(j); c[i+j-1]:=c[i+j-1]+a[i]*b[j]; until j>=k; dec(i); until i<=0; end; begin readln(n);a[1]:=2;b[1]:=1; writeln(2); l:=1; for i:=2 to n do begin fillchar(c,sizeof(c),0); chen; a:=c; for j:=1 to max do if a[j]>=100 then begin a[j+1]:=a[j+1]+a[j] div 100; a[j]:=a[j] mod 100; end; b:=a; inc(a[1]);j:=1; while a[j]>=100 do begin a[j+1]:=a[j+1]+a[j] div 100; a[j]:=a[j] mod 100; end; k:=maX; while a[k]=0 do dec(k); write(a[k]); for j:=k-1 downto 1 do if a[j]=0 then write('00') else begin t:=10; while a[j]<t do begin write('0'); t:=t div 10; end; write(a[j]); end; writeln; end; end. Thank you, I got AC! Couldn't find the bug in my first program, it gave the same results as yours up to test 10, after tha they were to big to check, but I rewrote it from scrap and got AC! please give me any trick for multiplying bignum ! i got tl and why solution for a(n) is... a(n)=pow(a(n-1),2)-a(n-1)+1; a(n)= a(n-1)^2-a(n-1) + 1 the way to do the problem is very easy, you see, the first fraction is obviusly the least which is 1/2 then you may want a fraction which is less than this last one but added with this leads to minimum left, so you may want a fraction the more likely to 1/2, this is 1/3 (2+1), then with this to add a third fraction, this will be 1/2 + 1/3 + ?, could be 1/6, but this leads to get a sum of 1, so the next will be 1/7 (2*3 + 1), the next will be 1/43 (2*3*7 + 1), the formula you put is a pretty factorization of this. There's a method to do multiplications on O(n^1.54), but i don't know how to do it exactly, you may want to see it in a book. Good Luck :) Miguel Angel. miguelangelhdz@hotmail.com An easyier way to get AC is to represent the bignums in base 1000. There is a lot of time saving an the modifications needed to be done when writing the output are easy (just add some 0s if a[j]<100 and a [j]<10). As for the O(N^1.58) algo, you were supposed to split the numbers into two halfs: A=C*10^n/2+D and B=E*10^n/2+F. G=(C+D)*(E+F)=C*E+D*F+C*F+D*E Then A*B=C*E*10^n+(G-C*E-D*F)*10^n/2+D*F We only hav to do 3 multiplications instead of 4 (G,C*E,D*F). In order to do these multiplication we use the same algorithm, until C,E,D,F on have one digit. or it's cheat? Hi CleverKid Can i meet you more? i see you have fast solution for problems and want to talk more my rating is now 397... i want to meet you more, so if you can mail me: aidin_n7@hotmail.com ~~~~~~~~~~ abour 1108 because it has just 18 input and it is very little range, cheating will be so easy! Bye |
|