ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

About problem 1114(Boxes)
Posted by Algorist 17 Dec 2001 16:33
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)
Posted by Algorist 18 Dec 2001 00:26
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
Posted by Algorist 18 Dec 2001 00:40
10549134770590785600
That's what the jury in the Bulgarian competition says. Test my prog
with long double. Make sure it works correctly....