ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

About problem 1114(Boxes)
Послано Algorist 17 дек 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)
Послано barsky 17 дек 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)
Послано Algorist 18 дек 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
Послано Algorist 18 дек 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....