Страница 1 there is my program var c:array[0..1800] of real; n,m,i ,fn:longint; begin readln(n,m); c[0]:=1; c[1]:=m-1; i:=1; repeat i:=i+1; {for i:=2 to n do } c[i]:=(m-1)*(c[i-1]+c[i-2]); until i>=n; writeln(c[n]:0:0); end. Because There is some testcases that have more than 1800 decimal digits.You should write Big int for this problem. there is my program var c:array[0..1800] of real; n,m,i ,fn:longint; begin readln(n,m); c[0]:=1; c[1]:=m-1; i:=1; repeat i:=i+1; {for i:=2 to n do } c[i]:=(m-1)*(c[i-1]+c[i-2]); until i>=n; writeln(c[n]:0:0); end. Use long arithmetics! Use long arithmetics! с этим не катит! всё равно WA #7 Send me your solution to my e-mail w_soulreaver[at]ukr[dot]net .And I'll try to help you! :) I send to you my solution as you know, it is forbidden to use math. but then how to use log? If you need ln try to use teylor series to calculate in manually... However, i think there isn't any nessesity for log... But I may be wrong, because i didn't solve this yet (solved only version 2). tell me wht doesn't this program work? or at least tell me an example that my program doesn't give us the right answer var l,n,k :integer; sum :longint; function c(a,b:integer):integer; var i,a1,b1,a1b1:integer; begin a1:=1; for i:=1 to a do a1:=a1*i; b1:=1; for i:=1 to b do b1:=b1*i; a1b1:=1; for i:=1 to a-b do a1b1:=a1b1*i; c:=a1 div (b1*a1b1); end; function power(r,s:integer):integer; var j,rs:integer; begin rs:=1; for j:=1 to s do rs:=rs*r; power:=rs; end; begin readln(n,k); l:=-1; while 2*l<=n do begin inc(l); inc(sum,(c(n-l,l)*power(k-1,n-l))); end; writeln(sum); end. Try with Big Numbers, no standart type will pass this problem as far as I remember,otherwise the idea I think is clear Orz, 拜大牛! I don't think it's possible. In FAQ it's written that minimal memory is over 100k because of compilator.Even only 2 variables need more than 2 k.And time is impossible to :) I really can't understand the reason. And 'vongang ' please respect others.Use English. Here is my code #include<stdio.h> long len[2],a[2][10000]; sum(int x) { int i; for(i=9999;i>=10000-len[(x)%2];i--) { a[(x-1)%2][i] = a[x%2][i] + a[(x-1)%2][i]; if(a[(x-1)%2][i]>=10) { a[(x-1)%2][i] = a[(x-1)%2][i]%10; a[(x-1)%2][i-1]++; if(i==10000-len[(x-1)%2]) len[(x-1)%2]++; } } return 0; } multiply(int x,int k) { int i,tod; tod=0; for(i=9999;i>=10000-len[(x-1)%2];i--) { a[(x-1)%2][i] = a[(x-1)%2][i] * k+tod; tod = 0; if(a[(x-1)%2][i]>=10) { tod = a[(x-1)%2][i]/10; a[(x-1)%2][i] = a[(x-1)%2][i]%10; if(i==10000-len[(x-1)%2]) len[(x-1)%2]++; } } return 0; } main() { long n,k,i,tmp; scanf("%ld %ld",&n,&k); a[0][9999] = 1; a[1][9999] = k-1; len[0] = 1; len[1] = 1; for(i=1;i<n;i++) { sum(i); multiply(i,k-1); } tmp = i; for(i=10000-len[tmp%2];i<=9999;i++) printf("%ld",a[tmp%2][i]); return 0; }
I think it's bad hint. That one is more harder. That's just great! I had WA on it after it was AC as 1012, then I was looking for mistakes for like half an hour! And finaly I submitted it with no changes and getting AC!!! #include <stdio.h> #include <mem.h> int num[2000],temp[2000],n,k,c1,c2; void jian() { int i,tw=0; for (i=1998;i>=0;i--) { if ((num[i]-temp[i]-tw)<0) {num[i]=10+num[i]-temp[i]-tw;tw=1;} else {num[i]=num[i]-temp[i]-tw;tw=0;} if (i<c2) {c2=i;break;} } } void cheng(int m) { int i,j,jw,t; for (i=1;i<=m;i++) { jw=0; for (j=1998;j>=0;j--) { t=temp[j]; temp[j]=(k*temp[j]+jw)%10; jw=(k*t+jw)/10; if ((j<=c1)&&(jw==0)) {c1=j;break;} } } i=1998; while (i>=0) { if (temp[i]>0) {temp[i]--;break;} else {temp[i]=9;i--;} } } int main() { int i,j; scanf("%d %d",&n,&k); c2=0; for (i=n;i>=1;i--) { for (j=0;j<=1998;j++) temp[j]=0; temp[1998]=1; c1=1998; cheng(i); if (i==n) for (j=0;j<=1998;j++) num[j]=temp[j]; else jian(); } for (i=0;i<=1998;i++) if (num[i]!=0) {j=i;break;} for (i=j;i<=1998;i++) printf("%d",num[i]); printf("\n"); return 0; } > #include <stdio.h> > #include <mem.h> > int num[2000],temp[2000],n,k,c1,c2; > void jian() > { > int i,tw=0; > for (i=1998;i>=0;i--) > { > if ((num[i]-temp[i]-tw)<0) {num[i]=10+num[i]-temp[i]-tw;tw=1;} > else {num[i]=num[i]-temp[i]-tw;tw=0;} > if (i<c2) {c2=i;break;} > } > } > void cheng(int m) > { > int i,j,jw,t; > for (i=1;i<=m;i++) > { > jw=0; > for (j=1998;j>=0;j--) > { > t=temp[j]; > temp[j]=(k*temp[j]+jw)%10; > jw=(k*t+jw)/10; > if ((j<=c1)&&(jw==0)) {c1=j;break;} > } > } > i=1998; > while (i>=0) > { > if (temp[i]>0) {temp[i]--;break;} > else {temp[i]=9;i--;} > } > } > int main() > { > int i,j; > scanf("%d %d",&n,&k); > c2=0; > for (i=n;i>=1;i--) > { > for (j=0;j<=1998;j++) temp[j]=0; > temp[1998]=1; > c1=1998; > cheng(i); > if (i==n) for (j=0;j<=1998;j++) num[j]=temp[j]; > else jian(); > } > for (i=0;i<=1998;i++) > if (num[i]!=0) {j=i;break;} > for (i=j;i<=1998;i++) > printf("%d",num[i]); > printf("\n"); > return 0; > } > #include <stdio.h> > #include <mem.h> > int num[2000],temp[2000],n,k,c1,c2; > void jian() > { > int i,tw=0; > for (i=1998;i>=0;i--) > { > if ((num[i]-temp[i]-tw)<0) {num[i]=10+num[i]-temp[i]-tw;tw=1;} > else {num[i]=num[i]-temp[i]-tw;tw=0;} > if (i<c2) {c2=i;break;} > } > } > void cheng(int m) > { > int i,j,jw,t; > for (i=1;i<=m;i++) > { > jw=0; > for (j=1998;j>=0;j--) > { > t=temp[j]; > temp[j]=(k*temp[j]+jw)%10; > jw=(k*t+jw)/10; > if ((j<=c1)&&(jw==0)) {c1=j;break;} > } > } > i=1998; > while (i>=0) > { > if (temp[i]>0) {temp[i]--;break;} > else {temp[i]=9;i--;} > } > } > int main() > { > int i,j; > scanf("%d %d",&n,&k); > c2=0; > for (i=n;i>=1;i--) > { > for (j=0;j<=1998;j++) temp[j]=0; > temp[1998]=1; > c1=1998; > cheng(i); > if (i==n) for (j=0;j<=1998;j++) num[j]=temp[j]; > else jian(); > } > for (i=0;i<=1998;i++) > if (num[i]!=0) {j=i;break;} > for (i=j;i<=1998;i++) > printf("%d",num[i]); > printf("\n"); > return 0; > } I use C, & I tryed to use unsigned long long with base 1e18, but it gives me Compilation Error, so I changed long long to int and then all works well. On gnu gcc 3.1 it works well also with long long. Isn't a iso/ansi c standard feature? What is the compiler used here? Compiler is Visual C++. Please use unsigned __int64. I made my array 10000, but still WA. type arr=array [1..10000] of byte; var p1,p2,p3,p4:arr; i,j,k,n,pos1,pos2,pos3,pos4:integer; procedure init; begin read(n,k); p2[1]:=1; p3[1]:=k-1; pos2:=1; pos3:=1; end; procedure plus(p1,p2:arr); var i:integer; begin fillchar(p4,sizeof(p4),0); for i:=1 to pos2 do begin inc(p4[i],p1[i]+p2[i]); if p4[i]>=10 then begin inc(p4[i+1],p4[i] div 10); p4[i]:=p4[i] mod 10; end; end; if pos1=pos2 then begin if p4[pos2+1]>0 then pos4:=pos2+1 else pos4:=pos2; end else pos4:=pos2; end; procedure multiply(m:integer;p4:arr); var i:integer; judge:boolean; begin fillchar(p3,sizeof(p3),0); for i:=1 to pos4 do begin inc(p3[i],m*p4[i]); if p3[i]>=10 then begin inc(p3[i+1],p3[i] div 10); p3[i]:=p3[i] mod 10; end; end; inc(i); judge:=true; while p3[i]>=10 do begin inc(p3[i+1],p3[i] div 10); p3[i]:=p3[i] mod 10; inc(i); judge:=false; end; if (judge)and(p3[i]=0) then pos3:=i-1 else pos3:=i; end; begin init; for i:=2 to n do begin p1:=p2; p2:=p3; pos1:=pos2; pos2:=pos3; plus(p1,p2); multiply(k-1,p4); end; for i:=pos3 downto 1 do write(p3[i]); writeln; end. 578757056862334899165386755574542961035018961384746496922121998413414 760578182667592445243789096415796683784227403924744723018491482416669 583482398922538253661908580120448244915999799871558380368176603050559 510718284952242760194267347067123980934918801967607536469254034237855 004802696022500822172028398423844181519062416396935137327709596075152 735669152169110801968382442244041567095126300108993003699366100747388 317910001503702242232876832468136833706279128186553604889872071700426 036131859303238586562176695339522070686158319498115704647672049305508 967900683916271481984259265546356412140086789757225512541731310323935 465682724467659536689371357372914882072915082178670642329922381122275 468063370016704705831888401388113877883071853045716833529742834352672 724383287190741642453977167289524175574818905457159394451552772137292 488320334403152854433233102668615521440710891545314660751974297836931 960344433170067572075073148241931611479767495629397929628139141880637 989092914568731174905142673360305672949338207556968549473017117468827 284519728547200726208072433397564194838002665675662311399400888368781 978474075164605331088146108539042375572214938643357857365785518398241 331586137392525667520443971761280252462702157845931972397850694852408 175842881290034219718513679989695433894555165544194154985658919590072 834353665620602624018084160454588232743604457892810545037909657962721 015357460269322147036550672667818736987298257001343500000127759081331 342259975035657526096273951774789390285967686426895591017628858005630 345299494887070844487552423092400976960882414257386427295509443688581 404929103326521825760465770078754255614451223600182778301246454644360 519407068303890382956047923339271967598500824214773103912508358944293 85287661810322936028474039484807146122948136437705880627901328134001 N + K <= 1800 !!! My answer is the same to you,but I got a WA program kbasednumbers; const max=500; osn=100000000; type big=array[0..max] of longint; var i:integer; a,b,c:big; n,k:word; procedure sumbig(var a,b,c:big); var k,i:word; begin FillChar(c,sizeof(c),0); if a[0]>=b[0] then k:=a[0] else k:=b[0]; for i:=1 to k do begin c[i+1]:=(a[i]+b[i]+c[i]) div osn; c[i]:=(a[i]+b[i]+c[i]) mod osn; end; if c[k+1]<>0 then c[0]:=k+1 else c[0]:=k; end; procedure multbignum(var a:big; number:word); var k,i:word; um,um_temp:longint; begin um:=0; for i:=1 to a[0] do begin um_temp:=(um+a[i]*number) div osn; a[i]:=(um+a[i]*number) mod osn; um:=um_temp; end; if um<>0 then begin inc(a[0]); a[a[0]]:=um; end; end; procedure printbig(var a:big); var nosn:word; s:string; begin str(osn div 10,s); nosn:=length(s); write(a[a[0]]); for i:=a[0]-1 downto 1 do begin str(a[i],s); while length(s)<nosn do s:='0'+s; write(s); end; end; begin read(n); read(k); a[0]:=1; a[1]:=1; b[0]:=1; b[1]:=k-1; for i:=2 to n do begin sumbig(a,b,c); multbignum(c,k-1); a:=b; b:=c; end; printbig(b); end. const nn=100; type my=array[1..nn]of integer; var a,b,c:my; n,k:integer; function dlina(a:my):integer; var i:integer; begin i:=nn; while a[i]=0 do dec(i); dlina:=i; end; procedure mul(a:my;var c:my); var i:integer; d:integer; begin fillchar(c,sizeof(c),0); d:=dlina(a); for i:=1 to d do c[i]:=a[i]*k; for i:=1 to d do if c[i]>9 then begin inc(c[i+1],c[i] div 10); c[i]:=c[i] mod 10; end; while c[d+1]<>0 do begin inc(d); if c[d]>9 then begin c[d+1]:=c[d] div 10; c[d]:=c[d] mod 10; end; end; end; procedure slog(a,b:my;var c:my); var d1,d2,max,i:integer; begin fillchar(c,sizeof(c),0); d1:=dlina(a); d2:=dlina(b); if d1>d2 then max:=d1 else max:=d2; for i:=1 to max do begin c[i]:=c[i]+a[i]+b[i]; if c[i]>9 then begin inc(c[i+1]); c[i]:=c[i] mod 10; end; end; end; procedure init; begin assign(input,''); reset(input); readln(n); readln(k); close(input); end; procedure solve; var i:integer; s:string; begin dec(k); str(k,s); for i:=1 to length(s) do c[i]:=ord(s[length(s)-i+1])-48; for i:=2 to n do begin a:=b; b:=c; slog(a,b,c); mul(c,c); end; slog(b,c,c); end; procedure out; var i:integer; begin assign(output,''); rewrite(output); for i:=dlina(c) downto 1 do write(c[i]); close(output); end; begin init; solve; out; end. F[N] = (k-1)*(F[N-1]); F[L] = (K-1)* (F[L-1] + F[L-2]); F[0] = 0; F[1] = K; Does it correct ? help me please. program p1013; const mx=120; type arr=array[1..mx] of longint; var a:array[0..1800] of arr; n,k,k1,t,i,j:integer; begin readln(n); readln(k); fillchar(a,sizeof(A),0); k1:=k-1; t:=1; while k1>0 do begin a[1,t]:=k1 mod 10; k1:=k1 div 10; inc(t); end; a[0,1]:=1; for i:=2 to n do begin for j:=1 to mx do a[i,j]:=a[i,j]+a[i-1,j]+a[i-2,j]; for j:=1 to mx do a[i,j]:=a[i,j]*(k-1); for j:=1 to mx do a[i,j+1]:=a[i,j+1]+a[i,j] div 10; for j:=1 to mx do a[i,j]:=a[i,j] mod 10; end; i:=50; while a[n,i]=0 do dec(i); for j:=i downto 1 do write(a[n,j]); writeln; end. > program p1013; > const mx=120; > type arr=array[1..mx] of longint; > var a:array[0..1800] of arr; > n,k,k1,t,i,j:integer; > > begin > readln(n); readln(k); > fillchar(a,sizeof(A),0); > k1:=k-1; t:=1; > while k1>0 do > begin > a[1,t]:=k1 mod 10; > k1:=k1 div 10; inc(t); > end; > a[0,1]:=1; > for i:=2 to n do > begin > for j:=1 to mx do a[i,j]:=a[i,j]+a[i-1,j]+a[i-2,j]; > for j:=1 to mx do a[i,j]:=a[i,j]*(k-1); > for j:=1 to mx do a[i,j+1]:=a[i,j+1]+a[i,j] div 10; > for j:=1 to mx do a[i,j]:=a[i,j] mod 10; > end; I think I typed a wrong sentence: > i:=mx; while a[n,i]=0 do dec(i); > for j:=i downto 1 do write(a[n,j]); > writeln; > end. Try to increase mx and don't use array a. You need only two last values. The algorithms I found requires O(N^2) , which N = 1800 . But we must calculate the large-number ( I use string) , so it takes about O (N^3) !!! . Could anyone help me on this Problem ? There is O(N) algorithm based on formula: f(n)=(k-1)*(f(n-2)+f(n-1)). 1 Don't use string, use int array. 2 use larger base to reduce the total operation 3 if C++, don't use STL long-number arithmetic? i thank that the resulting number is the next summ: N ___ i i \_ C *(K-1) /__ N-i
i=[N/2], where C is i!/((N-i)!*(2*i-N)!) and so we have to apply a long-number arithmetic,am I right? but it is no so fast for this problem!i get a time limit exceeded (it was worked for #1012) help me please maybe there are another faster algorithm? > long-number arithmetic? > i thank that the resulting number is the next summ: > N > ___ i i > \_ C *(K-1) > /__ N-i > > i=[N/2], where C is i!/((N-i)!*(2*i-N)!) > > and so we have to apply a long-number arithmetic,am I right? > but it is no so fast for this problem!i get a time limit exceeded > (it was worked for #1012) > help me please > maybe there are another faster algorithm? here is my program program ff; var n,i,j,k,l,t:integer; u0,u1,u2,a,b,c:array[0..2000] of byte; function max(a,b:integer):integer; begin if a>b then max:=a else max:=b; end; procedure sum(a,b:array of byte); begin l:=max(a[0],b[0]); fillchar(c,sizeof(c),0); t:=0; for i:=1 to l do begin c[i]:=(a[i]+b[i]+t) mod 10; t:=(a[i]+b[i]+t) div 10; end; c[0]:=l; if t<>0 then begin c[0]:=l+1; c[l+1]:=t; end; end; procedure mult(a:array of byte); begin l:=k-1; t:=0; fillchar(c,sizeof(c),0); for i:=1 to a[0] do begin c[i]:=(l*a[i]+t) mod 10; t:=(l*a[i]+t) div 10; end; c[0]:=a[0]; if t<>0 then begin c[0]:=a[0]+1; c[c[0]]:=t; end; end; procedure solve; begin u0[1]:=1; u0[0]:=1; u1[1]:=k-1; u1[0]:=1; for j:=2 to n do begin sum(u0,u1); u2:=c; mult(u2); u2:=c; u0:=u1; u1:=u2; end; end; begin readln(n,k); solve; for i:=u2[0] downto 1 do write(u2[i]); writeln; end. Страницы: Следующая 3 2 1 |
|