My idea is to solve it using DP of course. I have to use large
numbers for the result, unfortunately. Which means, that if I have an
array
50*500*sizeof(large num)
i'll have
25000*sizeof(large num)
large nums have about 100 digits, which is 100 bytes, so
25000*100=2500000=2 500 000 bytes, which is more than 1000K :(
If I use just recursion and do not store the results, I'll get time
limit exceeded.
My idea was to have the large numbers as
struct(=class=record) large {
 char* num;
 int size;
}
and allocate memory enough for each of the digits of every number.
The problem is that in C i have to use mallloc and realloc(I know I
can use new instead of malloc, but realloc is the real problem).
Realloc, however, doesn't work OK on my computer and on TIMUS, as I
have seen it :)) The strange fact is that if I trace the program, it
works fine, and if I run it -> it fails. I have the same problem on
another problem on timus, I do not remember which it was. Maybe
because I am allocating too much memory on too many pieces, which are
very small(a byte per time, about a million of times).

So, I help someone has read that,and that someone is going to help
about
1) What to use to solve the problem?
2) How can I solve the problem with realloc

> My idea is to solve it using DP of course. I have to use large
> numbers for the result, unfortunately. Which means, that if I have an
> array
> 50*500*sizeof(large num)
> i'll have
> 25000*sizeof(large num)
> large nums have about 100 digits, which is 100 bytes, so
> 25000*100=2500000=2 500 000 bytes, which is more than 1000K :(
> If I use just recursion and do not store the results, I'll get time
> limit exceeded.
> My idea was to have the large numbers as
> struct(=class=record) large {
>  char* num;
>  int size;
> }
> and allocate memory enough for each of the digits of every number.
> The problem is that in C i have to use mallloc and realloc(I know I
> can use new instead of malloc, but realloc is the real problem).
> Realloc, however, doesn't work OK on my computer and on TIMUS, as
I
> have seen it :)) The strange fact is that if I trace the program, it
> works fine, and if I run it -> it fails. I have the same problem on
> another problem on timus, I do not remember which it was. Maybe
> because I am allocating too much memory on too many pieces, which
are
> very small(a byte per time, about a million of times).
>
> So, I help someone has read that,and that someone is going to help
> about
> 1) What to use to solve the problem?
> 2) How can I solve the problem with realloc

> > My idea is to solve it using DP of course. I have to use large
> > numbers for the result, unfortunately. Which means, that if I
have an
> > array
> > 50*500*sizeof(large num)
> > i'll have
> > 25000*sizeof(large num)
> > large nums have about 100 digits, which is 100 bytes, so
> > 25000*100=2500000=2 500 000 bytes, which is more than 1000K :(
> > If I use just recursion and do not store the results, I'll get
time
> > limit exceeded.
> > My idea was to have the large numbers as
> > struct(=class=record) large {
> >  char* num;
> >  int size;
> > }
> > and allocate memory enough for each of the digits of every
number.
> > The problem is that in C i have to use mallloc and realloc(I know
I
> > can use new instead of malloc, but realloc is the real problem).
> > Realloc, however, doesn't work OK on my computer and on TIMUS, as
> I
> > have seen it :)) The strange fact is that if I trace the program,
it
> > works fine, and if I run it -> it fails. I have the same problem
on
> > another problem on timus, I do not remember which it was. Maybe
> > because I am allocating too much memory on too many pieces, which
> are
> > very small(a byte per time, about a million of times).
> >
> > So, I help someone has read that,and that someone is going to
help
> > about
> > 1) What to use to solve the problem?
> > 2) How can I solve the problem with realloc

Why did save all the result?
Just save 2*500*sizeof(large num).

Use round array