Discussion @ 1108. Heritage @ Timus Online Judge

Edric Mao why greedy is right? [4] // Problem 1108. Heritage 24 Aug 2010 16:06

DarkSun1997 Почему WA 1? [6] // Problem 1108. Heritage 14 Jul 2017 16:01

#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);
    }
}

Вот код, скорее всего он не пройдет макс тест, но при запуске на первом тесте он выдает мне в студии ответ правильный, а тут нет

Mahilewets Re: Почему WA 1? [4] // Problem 1108. Heritage 14 Jul 2017 16:25

Потому что первый тест не совпадает с примером.
Попробуйте отправить программу, которая выводит "2\n3\n" и вы убедитесь.

achpile Re: Почему WA 1? [3] // Problem 1108. Heritage 22 Jul 2017 13:42

ну у тебя и решение.... все ведь должно быть гораздо проще, хотя я тоже первый тест не могу пройти

#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;
}

Mahilewets Re: Почему WA 1? [2] // Problem 1108. Heritage 22 Jul 2017 15:04

По приколу, я сдал задачу.
[code deleted]

Edited by moderator 08.04.2020 21:07

Mahilewets Re: Почему WA 1? [1] // Problem 1108. Heritage 22 Jul 2017 15:06

http://acm.timus.ru/status.aspx?space=1&num=1108&author=201928
Думаю в ваших решениях overflow происходит.

Mahilewets Re: Почему WA 1? // Problem 1108. Heritage 22 Jul 2017 15:07

WA#1 у меня потому, что я проверял, действительно ли первый тест -- это N=2

MassterMax`~ Re: Почему WA 1? // Problem 1108. Heritage 22 Jan 2018 21:49

Я думаю, что здесь всего 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.

tiancaihb Java BigInteger... [1] // Problem 1108. Heritage 14 Aug 2009 08:43

Badd I can find the way to solve this problem but i can't use operate with bignum. Can anyone give me any trick or hint??? [3] // Problem 1108. Heritage 22 Feb 2002 20:17

SButterfly [Samara SAU] To admins // Problem 1108. Heritage 2 Apr 2015 22:16

OIdiot Why have I always got WA on #1 ? (python) [1] // Problem 1108. Heritage 4 Jan 2015 18:25

YSYMYTH Who knows about java? [2] // Problem 1108. Heritage 3 Jul 2012 20:40

Rafikov Ramil AC --WITHOUT CHEATING-- in 0.156s (361 kb) [1] // Problem 1108. Heritage 20 Oct 2009 21:49

Hanzbrow (TNU) KCC algorithm // Problem 1108. Heritage 18 Sep 2009 00:14

And IV CRAZY [1] // Problem 1108. Heritage 11 Jul 2007 15:22

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

Dmitry "Logam" Kobelev [TSOGU] Re: CRAZY // Problem 1108. Heritage 30 Aug 2008 12:35

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

Romko [Lviv NU] Why this code can't got AC? [2] // Problem 1108. Heritage 12 Mar 2007 21:37

Simonenko Vladislav 0.031 sec and got ACCEPTED [5] // Problem 1108. Heritage 10 Jun 2004 14:22

Renato Baba For N = 18, how large will the last number of the answer be? (-) [2] // Problem 1108. Heritage 19 Feb 2002 03:34

longzeling88 How about n=1? [1] // Problem 1108. Heritage 30 Aug 2004 19:59

Nazarov Denis (nsc2001@rambler.ru) It is imposible to solve this problem with time < 5 sec with honest program! [6] // Problem 1108. Heritage 11 Jan 2002 15:18

lz will the church get the heritage like the form 1/k? [1] // Problem 1108. Heritage 4 Aug 2003 13:03

Vlad Ionescu Please help!!! (almosat correct program inside) [2] // Problem 1108. Heritage 2 Jul 2003 21:24

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.

ACer Re: Here is my AC solution,I think it can help you [1] // Problem 1108. Heritage 4 Jul 2003 20:49

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.

Vlad Ionescu Thank you! // Problem 1108. Heritage 9 Jul 2003 07:22

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!

TheBlaNK please give me any trick for multiplying bignum ! i got tl and why solution for a(n) is... [2] // Problem 1108. Heritage 16 Apr 2002 15:27

CleverKid Is there RELLY an o(n) algorithm? [3] // Problem 1108. Heritage 24 Jan 2003 16:45

Reshetnikov Eugeny Please give me method or program, what multiple 2 bignum for O(N^1.5)! My E-Mail: Resolver@Ufacom.ru. Please. It's needly for me! // Problem 1108. Heritage 18 Jan 2003 00:52

Discussion of Problem 1108. Heritage