I used high-precision and recursion... but I get WA at test 4.... but if I input 170 10,the answer on my local is correct... please someone give me a test case to test my program? sorry,I know why...It's the high-percision I designed is wrong... I store each 3 digit of the orginal number in a int,but when I output the number,I forgot to insert 0 before the int which digit is less than 3. sorry for my english... why wa#1 ??? #include <cstdlib> #include <iostream> using namespace std; int a[2000],b[2000]; int c[2000][2000]; int en; int sum(int k,int p) { int top[4000]; int i,j=0; int y=0,t;
if (k > p) { for (i=k;i>=k-p;i--) b[i]=b[i-(k-p)]; for (i=0;i<k-p;i++) b[i]=0; en=k; } else if (p > k) { for (i=p;i>=p-k;i--) a[i]=a[i-(p-k)]; for (i=0;i<p-k;i++) a[i]=0; en=p; } else if (k == p) en=k;
for (i=en-1;i>=0;i--) { t=a[i]+b[i]+y; if (t > 9) { t-=10; y=1; top[j]=t; j++; } else {top[j]=t; j++; y=0;} } if (y == 1) {top[j]=y; j++;} int l=0; for (i=j-1;i>=0;i--) { a[l]=top[i]; l++; } return l; } int multi(int k,int p,int n) { int tp[5000]; int cv[4000]; int y=0,v=0,vy,uz; int i,l=0,j,sy=0;
for (i=0;i<=4000;i++) tp[i]=0; for (i=k-1;i>=0;i--) { v=(a[i]*p)+vy; if (v > 9) { vy=v / 10; v-=(vy*10); } else vy=0; cv[l]=v; l++; if (vy > 0) {cv[l]=vy; l++;} l+=sy; for (j=l-1;j>=sy;j--) cv[j]=cv[j-sy]; for (j=0;j<sy;j++) cv[j]=0; for (j=0;j<l;j++) { uz=l-1; tp[j]+=cv[j]+y; if (tp[j] > 9) { tp[j]-=10; y=1; } else y=0; } for (j=0;j<l;j++) cv[j]=0; if (y == 1) { uz++; tp[uz]=y; } l=0; vy=0; sy++; y=0; } l=0; while (tp[uz] <= 0) uz--; for (j=uz;j>=0;j--) { c[n][l]=tp[j]; l++; } return l; } int main() { int n,k,i,j,u; int uz[2000];
cin>>n>>k; c[0][0]=1; c[1][0]=k-1; uz[0]=1; uz[1]=1; for (i=2;i<=n;i++) { for (j=0;j<uz[i-1];j++) a[j]=c[i-1][j]; for (j=0;j<uz[i-2];j++) b[j]=c[i-2][j]; u=sum(uz[i-1],uz[i-2]); uz[i]=multi(u,k-1,i); }
for (i=0;i<uz[n];i++) cout<<c[n][i]; cout<<endl;
return EXIT_SUCCESS; } What's wrong??? What's 6 WA??? Why??? My programm enables big numbers!!! Could you tell me some tests with right answers? #include<stdio.h> #include<stdlib.h> #include<conio.h> #include<string.h> char* add(char *p1, char *p2) { char *p; char temp=0, end1=0, end2=0; int len,i; len=strlen(p1)>strlen(p2)?strlen(p1)+2:strlen(p2)+2; p=(char *)malloc(len*sizeof(char)); for(i=0; i<len-1; ++i) { if(!p1[i]) end1=1; if(!p2[i]) end2=1; if(end1&&end2&&!temp) break; if(!end1) temp+=(p1[i]-'0'); if(!end2) temp+=(p2[i]-'0'); p[i]=temp%10+'0'; temp/=10; } p[i]=0; while(p[--i]=='0'&& &p[i]!=p) p[i]=0; return p; } char* sub(char *p1, char *p2) { char *p; char temp=0, end1=0, end2=0; int len,i; len=strlen(p1)>strlen(p2)?strlen(p1)+2:strlen(p2)+2; p=(char *)malloc(len*sizeof(char)); for(i=0; i<len-1; ++i) { if(!p1[i]) end1=1; if(!p2[i]) end2=1; if(end1&&end2&&!temp) break; if(!end1) temp+=(p1[i]-'0'); if(!end2) temp-=(p2[i]-'0'); p[i]=(temp+100)%10+'0'; if(temp<0) { temp/=10; temp--; } else temp=0; } p[i]=0; while(p[--i]=='0'&& &p[i]!=p) p[i]=0; return p; } char* mul(char *p1, int k) { char *p; char temp=0, end1=0; int len,i; len=strlen(p1)+2; p=(char *)malloc(len*sizeof(char)); if(k==10) { p[0]='0'; p[1]=0; strcat(p,p1); return p; } for(i=0; i<len-1; ++i) { if(!p1[i]) end1=1; if(end1&&!temp) break; if(!end1) temp+=(p1[i]-'0')*k; p[i]=temp%10+'0'; temp/=10; } p[i]=0; while(p[--i]=='0'&& &p[i]!=p) p[i]=0; return p; } void printb(char *p) { int i; for(i=strlen(p)-1;i>=0; i--) printf("%c", p[i]); } int main() { int N, K; int i; char* result, *t1, *t2; char* Nulls[2000];
printf("Enter N and K: "); scanf("%d%d",&N,&K);
Nulls[0]="0"; result=(char *)malloc(2*sizeof(char)); result[0]=K-1+'0'; result[1]=0; try { for(i=1; i<N;++i) { Nulls[i]=sub(result,Nulls[i-1]); t1=mul(Nulls[i],K); t2=mul(Nulls[i-1],(K-1)); result=add(t1,t2); free(t1); free(t2); } } catch(...) { printf("Error"); while(!kbhit()); return 0; } printf("Result = "); printb(result); free(result); while(!kbhit()); return 0; } I wanted to put my solution , but I had some problem Sorry Kula meybe you didn't take my solution write here your e-mail adress I'll send you Edited by author 08.02.2006 14:05 kazaxam respect! Edited by author 08.02.2006 16:43 Edited by author 08.02.2006 16:43 Edited by author 09.02.2006 16:39 A SIng song Edited by author 08.02.2006 09:25 Edited by author 08.02.2006 09:25 Edited by author 08.02.2006 17:47 why in here wrong answer in 6 var c:array[0..50] of integer; n,m,i ,fn:longint; begin readln(n,m); c[0]:=1; c[1]:=m-1; for i:=2 to n do c[i]:=(m-1)*(c[i-1]+c[i-2]); writeln(c[n]); end. longint is not enough but how i can do array with extended??? var c:array[0..180] 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. program t1012; var a,b,n,k,i,j,l,p,q,c,d,o:longint; f,h:array [0..10000] of string; s,x,m:string; begin readln(n); readln(k); str(k-1,m); f[0]:=m; val(f[0],a,b); str(k*a,m); f[1]:=m;l:=1; for i:=2 to n do begin a:=length(f[i-1]); b:=length(f[i-2]); if a>b then d:=a else d:=b; x:=f[i-1];m:=f[i-2]; if d=a then for j:=a-b downto l do m:=concat('0',m); if d=b then for j:=b-a downto l do x:=concat('0',x); for j:=d downto l do begin val(x[j],p,o); val(m[j],q,o); b:=p+q+c; c:=b div 10; q:=b mod 10; str(q,h[j]); if j=l then if c>0 then begin dec(l);str(c,h[l]); end; p:=0;q:=0; end; c:=0; for j:=l to d do s:=concat(s,h[j]); l:=1; for j:=d downto l do begin val(s[j],p,o); b:=p*9+c; c:=b div 10; q:=b mod 10; str(q,h[j]); if j=l then if c>0 then begin dec(l);str(c,h[l]); end; p:=0;q:=0; end; c:=0; s:=''; for j:=l to d do s:=concat(s,h[j]); l:=1; f[i]:=s; s:=''; end; writeln(f[n-1]); end. когда я с длинной арифметикой сделал эту задачу я использовал в качестве основы 10000 и у меня был WA#7 тест потом я сделал снову 10 и у меня был WA#2 тест тогда подумав решил использовать EXTENDED всеравно WA#6 тест кто подскажет как преодолеть 2, 6, 7 тесты Use base = 10 compare small answers with 1009 I compaired it My program gives equal answers in all cases Чёрт его знает Use Java's BigInteger I always use it then long arifmetic is needed. Помоему он подсовывает во 2 тесте N=170 и K=10 Если умножать пллучается 10 с 170 нулями. Никакой тип не выдержит. Надо разбивать число на группы. Только какие? Edited by author 11.06.2008 17:47 174568663359808123517619015636369512622213 064344534689513998708986681415716975079951 752754958954321404709642918328732491072229 658639887075761909680804620151071937764270 946419913401 Edited by author 29.10.2008 11:30 In English K<=10. in Russian K<10. What is K??? Sorry , it work's now. )) Edited by author 07.09.2008 15:46 I wrote this problem with LA,it answers correct to all my tests,but gets WA2.I submitted it for 1009 and also got WA2! Then I checked ALL POSSIBLE TESTS for 1009 ,and it answered correct to all of them!!!Just cant imagine WHY I GET WA !!! Edited by author 01.07.2008 13:17 in my programm I added this: if(k==1) {cout<<0;return 0;} if(n==1) {cout<<k-1;return 0;} according to problem statement,n>=2,k>=2,so this cases are impossible,but here I got WA1,when without this cases I got WA2!! OK,I found my bug (AC now),but I still dont understand why this two cases were making problems. I've got 1013 C++ Accepted 0.062 439 КБ with a help of such construction: huge f[5]; int i,n,k; char c[2]; cin>>n>>k; cin.getline(c,1); f[0].d[0]=1; f[0].len=1; f[1].len=1; f[1].d[0]=k-1; for(i=2;i<=n;i++) { f[i%5]=(f[(i-1)%5]+f[(i-2)%5])*(k-1); } f[n%5].output(); return 0; this is int main() code Here huge f[5] is an array of long arithmetic classes in which i used overloaded operators "+" and "*" This code REALLY works It is memory-economical code :-) Edited by author 07.11.2007 01:35 Edited by author 07.11.2007 01:38 #include<stdio.h> long int n,k,f1[200],f2[200],f3[200],i,j,t,c; void main() { scanf("%ld",&n); scanf("%ld",&k); f1[0]=1; f2[0]=k-1; t=1; for(i=2;i<=n;i++) for(j=0;j<t;j++) { if((k-1)*(f1[j]+f2[j]+c)>999999&&j==t-1) {t++; f3[t]= (k-1)*(f1[j]+f2[j]+c)-(k-1)*(f1[j]+f2[j]+c)%999999; } else if((k-1)*(f1[j]+f2[j]+c)>999999) { c= (k-1)*(f1[j]+f2[j]+c)-(k-1)*(f1[j]+f2[j]+c)%999999; } else c=0; f3[j]=(k-1)*(f1[j]+f2[j]+c); f1[j]=f2[j]; f2[j]=f3[j]; } for(j=t-1;j>=0;j--) printf("%ld",f3[j]); } Try to solve it with long arithmetics... Delete if's and then in a unique repeat function use long arithmetics and that's all.don't increase t just bind t:=j; and you will get AC... also the sizes of arrays are 2000 and you should print the 2nd array i mean f2 not f3. good luck! P.S. if you have questions i'll be glad to help you... #include<iostream> #include<cstdio> using namespace std; int solve(int n,int k){ unsigned long long a[3]={0}; a[0]=1; a[1]=k-1; for(int i=2;i<=n;i++) a[i%3]=(k-1)*(a[(i-1)%3]+a[(i-2)%3]); printf("%I64u\n",a[n]); return 0; } int main() { int n,k; //while(1){ scanf("%d%d",&n,&k); solve(n,k); //} return 0; } Хотя юзаю длинную... У кого нить была такая проблема? как исправили? What does "k-based number" and "successful zeroes" means in Chinese? "k-based number" means "K进制数" "successful zeroes" means "连续的零" program ural_1012; var a1,a0,p:longint; n,k,i:integer; begin readln(n,k); a1:=k-1; for i:=2 to n do begin p:=a1; a1:=(a1+a0)*(k-1); a0:=p; end; writeln(a1+a0); end. Because you are very ugly! ~~~~ Edited by author 21.07.2007 16:48 you can look var a1,a0,p:extended; n,k,i:extended; begin readln(n,k); a1:=k-1; i:=1; {for i:=2 to n do begin } repeat i:=i+1; p:=a1; a1:=(a1+a0)*(k-1); a0:=p; until i>=n; {end; } writeln(a1+a0:0:0); end. You way are currect but you MUST use HI-precision #include<iostream.h> #include<stdio.h> int main() { int n,i,k;unsigned __int64 a[2000],p; cin>>n>>k;a[1]=k-1;a[2]=k*(k-1); for(i=3;i<=n;i++) {a[i]=(k-1)*(a[i-1]+a[i-2]);p=a[i];} if(n==1) cout<<k-1; else if(n==2) cout<<k*(k-1); else if(n>=3) printf("%I64u", p); return 0; } You should use long arithmetic!!! CAN I SOLVE IT WHITOUT LONG ARITHMETIC?THANK!!! 1)hacking ;) - bad way 2)find answers for all test cases but more easy to write LA Edited by author 11.04.2007 18:10 I have the solution!!! do you want var a,b:array[1..1000]of longint; i,n,k,u,v,j:longint; begin for i:=1 to 100 do begin a[i]:=0; b[i]:=0; end; readln(n); readln(k); a[1]:=k-1; b[1]:=k*(k-1); u:=1; v:=1; for i:=3 to n do if (i mod 2=1) then for j:=1 to v do begin if 9*(a[j]+b[j])>=1000000000 then begin if j=v then u:=u+1; a[j+1]:=a[j+1]+1; end; a[j]:=9*(a[j]+b[j]) mod 1000000000 end else for j:=1 to u do begin if 9*(a[j]+b[j])>=1000000000 then begin if j=u then v:=v+1; a[j+1]:=a[j+1]+1; end; a[j]:=9*(a[j]+b[j]) mod 1000000000 end; if n mod 2=1 then for i:=u downto 1 do write(a[i]) else for i:=v downto 1 do write(b[i]); end. |
|