Show all threads Hide all threads Show all messages Hide all messages | Page 1 | why WA in 6 | zzzlll | 1013. K-based Numbers. Version 3 | 21 Mar 2010 18:34 | 2 | 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. | why WA in 6 | zzzlll | 1013. K-based Numbers. Version 3 | 9 Mar 2007 15:40 | 5 | 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! с этим не катит! всё равно 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 | how can i use log (or ln) without math header | starforever | 1013. K-based Numbers. Version 3 | 27 Dec 2006 20:52 | 3 | 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). | a program | math404_3140 | 1013. K-based Numbers. Version 3 | 12 Aug 2006 20:11 | 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 | Is it possible ? | Todor Tsonkov | 1013. K-based Numbers. Version 3 | 12 Jan 2012 01:38 | 7 | 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. | Help Please WA#8 | ABCDE | 1013. K-based Numbers. Version 3 | 24 Mar 2006 16:12 | 1 | 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; }
| Hint: Solve first 1081 | Vlad Saveluc (lexgas) | 1013. K-based Numbers. Version 3 | 31 Aug 2006 13:08 | 2 | I think it's bad hint. That one is more harder. | Problems with judge! | Андрей Макуха | 1013. K-based Numbers. Version 3 | 29 Jun 2004 03:04 | 1 | 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!!! | Why my program is Compilation Error? | hls | 1013. K-based Numbers. Version 3 | 7 Aug 2003 11:22 | 3 | #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; > } | what compiler? | ste | 1013. K-based Numbers. Version 3 | 28 Jun 2008 20:23 | 2 | 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. | Why my AC 1012 program WA at 1013 | Fu Jieyun | 1013. K-based Numbers. Version 3 | 9 Jun 2003 08:48 | 1 | 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. | If you want to check your program here is answer for n=1800 k=10 | Nickolas | 1013. K-based Numbers. Version 3 | 26 Oct 2008 13:15 | 3 | 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 My answer is the same to you,but I got a WA | Filippov Nickolas SSAU#2's AC program is HERE! | Nickolas | 1013. K-based Numbers. Version 3 | 14 Feb 2003 19:48 | 1 | 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. | Help !!! Why Memory Limit ???????? | GodZilla | 1013. K-based Numbers. Version 3 | 24 Dec 2002 20:21 | 1 | 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. | is my recursive relation correct ? please help me. | Accepted | 1013. K-based Numbers. Version 3 | 3 Dec 2002 16:55 | 1 | 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. | Help! I Use this program to AC 1009, but can't AC this! | Dr.J.Pascal | 1013. K-based Numbers. Version 3 | 19 Aug 2004 12:04 | 5 | 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. | How can I pass the time limit ? Please help me !!! | Nguyen Viet Bang | 1013. K-based Numbers. Version 3 | 27 Aug 2002 18:03 | 3 | 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???? | guseva polina | 1013. K-based Numbers. Version 3 | 6 Jun 2002 06:51 | 2 | 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? | can anybody help me with my WA? | Shota Gvinepadze | 1013. K-based Numbers. Version 3 | 2 Dec 2001 17:46 | 1 | 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. | Shall I print the answer in one line? | Mao YanDong | 1013. K-based Numbers. Version 3 | 28 Sep 2001 05:39 | 2 | |
|
|