Common BoardAbout problem 1114(Boxes) Here is my source code. I have tried it at all the largest values of the input. I am sure it works, moreover. I test it using the tests given at the Bulgarian contest itself - everything is fine. Anyone can tell my where the mistake is? #include <stdio.h> #define UNDEFINED 0 #define MAXBOX 22 #define MAXR 16 #define MAXB 16 long double ways[MAXBOX][MAXR][MAXB]; int box,red,blue; FILE *f; void init(void) { int i,j,k; f = stdin; // f = fopen(fin,"r"); fscanf(f,"%d %d %d",&box,&red,&blue); // fclose(f); for (i=1;i<=box;i++) for (j=0;j<=red;j++) for (k=0;k<=red;k++) ways[i][j][k]=UNDEFINED; for (i=0;i<=red;i++) for (j=0;j<=blue;j++) ways[0][i][j]=1; } long double solve(int boxes,int r,int b) { int i,j; long double sum=0; if (ways[boxes][r][b]!=UNDEFINED) return ways[boxes][r][b]; for (i=0;i<=r;i++) for (j=0;j<=b;j++) { sum+=solve(boxes-1,r-i,b-j); } ways[boxes][r][b]=sum; return ways[boxes][r][b]; } int main(void) { init(); f = stdout; // f = fopen(fout,"w"); solve(box,red,blue); fprintf(f,"%0.0Lf\n",ways[box][red][blue]); return 0; } Re: About problem 1114(Boxes) Posted by barsky 17 Dec 2001 18:00 > Here is my source code. I have tried it at all the largest values of > the input. I am sure it works, moreover. I test it using the tests > given at the Bulgarian contest itself - everything is fine. Anyone > can tell my where the mistake is? > I see it gives also true answer whith small valoes. But really you sure whith big values? For example: 10549134770590783000 for 20 15 15 ? long double have 17 correct numbers + exp, you see this example have 17 numbers whith exp(10^3). 1937496182353408500 for 20 14 14 and 4521057758824627700 for 20 15 14 isn't correct (its my opinion) because i tested your programm using __int64 and have: 1937596182353409600 for 20 14 14 and 4521057758824622400 for 20 15 14 1937596182353409600 != 1937496182353408500 Sorry i can't tested 20 15 15 bacause it's more than __int64. I think that __int64 more correct than long double. //Mail to barsky@students.ru if you want answer this message. //Your code whith __int64 //Use Visual C++ Version 6.0 //Programm don't works whith 20 15 15 test #include <stdio.h> #include <iostream.h> #define UNDEFINED 0 #define MAXBOX 22 #define MAXR 16 #define MAXB 16 __int64 ways[MAXBOX][MAXR][MAXB]; int box,red,blue; FILE *f; void init(void) { int i,j,k; f = stdin; // f = fopen(fin,"r"); fscanf(f,"%d %d %d",&box,&red,&blue); // fclose(f); for (i=1;i<=box;i++) for (j=0;j<=red;j++) for (k=0;k<=red;k++) ways[i][j][k]=UNDEFINED; for (i=0;i<=red;i++) for (j=0;j<=blue;j++) ways[0][i][j]=1; } __int64 solve(int boxes,int r,int b) { int i,j; __int64 sum=0; if (ways[boxes][r][b]!=UNDEFINED) return ways[boxes][r][b]; for (i=0;i<=r;i++) for (j=0;j<=b;j++) { sum+=solve(boxes-1,r-i,b-j); } ways[boxes][r][b]=sum; return ways[boxes][r][b]; } int main(void) { init(); f = stdout; // f = fopen(fout,"w"); solve(box,red,blue); //fprintf(f,"%0.0Lf",ways[box][red][blue]); //cout<< ways[box][red][blue] ; __int64 o = ways[box][red][blue]; int out[1000]; int n = 0; while(o != 0) { out[n] = o%10; n++; o /= 10; } int a; for(a = n-1; a!=-1;a--) printf("%d", out[a]); //scanf("%d", &a); return 0; } //Mail to barsky@students.ru if you want answer this message. Re: About problem 1114(Boxes) No, I am sure. I have the jury tests, and so I have the answer for 20 15 15. And my program gives correct answer. And I think is that 20 15 15 is the largest number possible. But long double CAN store such a large number. So, the problem isn't is the correctness of the solution in my opinion. Maybe the server's compiler cannot compile my source as I can when I am home. I do not know. Maybe Marat Bakirov should look at this.... Btw what compiler do timus use???? > > Here is my source code. I have tried it at all the largest values > of > > the input. I am sure it works, moreover. I test it using the tests > > given at the Bulgarian contest itself - everything is fine. Anyone > > can tell my where the mistake is? > > > > I see it gives also true answer whith small valoes. > But really you sure whith big values? > For example: 10549134770590783000 for 20 15 15 ? > long double have 17 correct numbers + exp, you see this example have > 17 numbers whith exp(10^3). > 1937496182353408500 for 20 14 14 and > 4521057758824627700 for 20 15 14 > isn't correct (its my opinion) because i tested your programm using > __int64 and have: 1937596182353409600 for 20 14 14 > and 4521057758824622400 for 20 15 14 > 1937596182353409600 != 1937496182353408500 > Sorry i can't tested 20 15 15 bacause it's more than __int64. > I think that __int64 more correct than long double. > > > //Mail to barsky@students.ru if you want answer this message. > //Your code whith __int64 > //Use Visual C++ Version 6.0 > //Programm don't works whith 20 15 15 test > > #include <stdio.h> > #include <iostream.h> > > #define UNDEFINED 0 > #define MAXBOX 22 > #define MAXR 16 > #define MAXB 16 > > __int64 ways[MAXBOX][MAXR][MAXB]; > int box,red,blue; > FILE *f; > > > void init(void) { > int i,j,k; > f = stdin; > // f = fopen(fin,"r"); > fscanf(f,"%d %d %d",&box,&red,&blue); > // fclose(f); > for (i=1;i<=box;i++) > for (j=0;j<=red;j++) > for (k=0;k<=red;k++) > ways[i][j][k]=UNDEFINED; > for (i=0;i<=red;i++) > for (j=0;j<=blue;j++) > ways[0][i][j]=1; > } > > __int64 solve(int boxes,int r,int b) { > int i,j; > __int64 sum=0; > if (ways[boxes][r][b]!=UNDEFINED) return ways[boxes][r][b]; > for (i=0;i<=r;i++) > for (j=0;j<=b;j++) { > sum+=solve(boxes-1,r-i,b-j); > } > ways[boxes][r][b]=sum; > return ways[boxes][r][b]; > } > > int main(void) { > init(); > f = stdout; > // f = fopen(fout,"w"); > solve(box,red,blue); > //fprintf(f,"%0.0Lf",ways[box][red][blue]); > //cout<< ways[box][red][blue] ; > __int64 o = ways[box][red][blue]; > int out[1000]; > int n = 0; > while(o != 0) > { > out[n] = o%10; > n++; > o /= 10; > } > int a; > for(a = n-1; a!=-1;a--) > printf("%d", out[a]); > //scanf("%d", &a); > return 0; > } > > > //Mail to barsky@students.ru if you want answer this message. And, even more, here is the jury solution for 20 15 15 10549134770590785600 That's what the jury in the Bulgarian competition says. Test my prog with long double. Make sure it works correctly.... |