495 - Fibonacci Freeze

[smilitude]

man, you are awesome!
thanks a lot!

[Schutzstaffel]

I'm also getting RE, I've tested my code with big numbers and also with number 5000 and it doesn't crash so what's the reason for this RE? I've also delcared big arrays as global.

Code: Select all

 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define max(a,b) ((a>b)? a: b)

typedef struct{
  int *digits;
  unsigned int size;
  unsigned int flag;
} bigInt, *bigIntp;

bigInt results[5001];
char n[1100];
char nn[1101];
bigIntp n1;
bigIntp n2;
bigIntp res;
bigIntp a;
bigIntp b;
bigIntp sum;

bigIntp create(unsigned int size)
{
  bigIntp big = malloc(sizeof(bigInt));
  big->digits = malloc(sizeof(int)*size);
  big->size = size;
  big->flag = 0;
  return big;
}

void destroy(bigIntp b)
{
  free(b->digits);
  free(b);     
}

void convertInt(char *n, bigIntp big)
{
  unsigned int size = strlen(n)-1;
  unsigned int i,j;
  char c[2];
  for(i = size, j = 0; i > 0; i--,j++)
  {
    c[0] = n[i];
    c[1] = '\0';
    big->digits[j] = atoi(c);
    big->flag++;
  }
  c[0] = n[i];
  c[1] = '\0';
  big->digits[j] = atoi(c);
  big->flag++;
  if(size < big->size)
  {
    for(i = j+1; i<big->size; i++)
    {
      big->digits[i] = 0;
    }
  }
}

void sumBigInt(bigIntp a, bigIntp b, bigIntp sum)
{
  unsigned int i;
  unsigned int remainder = 0;
  unsigned int m = max(a->flag,b->flag) + 1;
  sum->flag = max(a->flag,b->flag);
  for(i = 0; i < a->size; i++)
  {
    sum->digits[i] = a->digits[i] + b->digits[i] + remainder;
    remainder = sum->digits[i]/10;
    sum->digits[i] %= 10;
    if(sum->digits[i] != 0)
      if(i == m-1)
        sum->flag++;
  }  
}

void printBigInt(bigIntp big)
{
  int i;
  for(i = big->flag-1; i >=0; i--)
    printf("%d",big->digits[i]);
  printf("\n");
}

int main(void)
{
  int i,k,j;
  a = create(1100);
  b = create(1100);
  sum = create(1100);
  n1 = create(1100);
  n2 = create(1100);
  convertInt("0",a);
  convertInt("1",b);
  memcpy(&results[0],a,1100);
  memcpy(&results[1],b,1100);
  
  for(i = 2; i <=5000; i++)
  {
    memcpy(n1, &results[i-1],1100);
    memcpy(n2, &results[i-2],1100);
    sumBigInt(n1,n2,sum);
    for(k = sum->flag-1, j= 0; k>=0; k--,j++)
    {
      sprintf(&nn[j],"%d",sum->digits[k]);
    }
    res = create(1100);
    convertInt(nn,res);
    memcpy(&results[i],res,1100);
  }
  while(scanf("%s\n",n) == 1)
  {
    printf("The Fibonacci number for %s is ",n);
    i = atoi(n);
    printBigInt(&results[i]);
  }
  destroy(a);
  destroy(b);
  destroy(n1);
  destroy(n2);
  destroy(sum);
  destroy(res);
  return 1;
}

Any help is appreciated, thanks.

[chunyi81]

Try this test case:

Input:
0
1
2

Correct Output is:
The Fibonacci number for 0 is 0
The Fibonacci number for 1 is 1
The Fibonacci number for 2 is 1

But your code prints:
The Fibonacci number for 0 is
The Fibonacci number for 1 is
The Fibonacci number for 2 is

This could be the reason for your RE. If the inputs are 3 or bigger then your program outputs the right answer.

[Schutzstaffel]

Thank you!
That was in fact a problem, I had the cycle condition in the print function wrong plus incremented wrongly the flag variable in the sum function.
I still get RE though
Any idea of what it might be? It doesn't crash in my pc and all array indexs seem to be valid through the program execution and the size seems to be enough. I edited the previous posted code with the corrected one to avoid repeting the same code.
Thanks.

[smilitude]

dearest,
i am a C programmer, recently(last few days) i am looking forward for CPP. though i cant help you, may i ask you, is it really needed to dynamically allocate those memories? may be you can keep the program simple and less obscure if you avoid those parts. Well, plz dont mind on my words, but i think that will help you to debug!
never mind, i am a novish to cpp.

[Schutzstaffel]

If you're using pointers yes, if not it's not necessary. Do I need to use pointers to solve the problem? Not really but the bigInt is from a library I'm making for big integers and thus I made it as flexibly as possible (yet it's still incomplete and not perfect).
I think I've tested the code enough to believe there's no memory violation nor memory allocation problems but still I'm not 100% sure and since I read that big arrays must be declared as static or global I was wondering if my problem might be coming for something similar since it works on my PC.
Thanks

[chunyi81]

Now your code does not even given any output and crashes with a segmentation fault on my PC. I ran your code in Unix, which is why this type of crash may occur.

Running your code with a debugger shows that your code crashed at this line:

Code: Select all

sum->digits[i] = a->digits[i] + b->digits[i] + remainder;

Try increasing the array size for the number of digits

[Schutzstaffel]

I've been debugging the code now in Linux and noticed that if I pre-calculated the numbers untill 4700th it worked okay but then if I tried 4800 (I increase 100 numbers in each try so I don't know the correct value) it crashed I laso tried to increse the digits numbers by 1000 (2100 digits total) and still it crashes. I'm clueless what it might be
Thanks for your help and for telling me the line.

[chunyi81]

Check these lines:

Code: Select all

bigIntp big = malloc(sizeof(bigInt)); 
  big->digits = malloc(sizeof(int)*size); 

You allocate space for big first and then the space for the digits, change
bigIntp big = malloc(sizeof(bigInt));

to

bigIntp big = malloc(size*4 + 8 );

A C int is 4 bytes in size

In the memcpy functions you used, change the third parameter to 4408

The RE should go away.

And the array size you initially used for digits, which is 1100, is enough.

Hope this helps.

[poti]

type digits = shortint;
number = record v: array[1..1100] of digits; q:integer end;
var DP: array[0..5000] of number;
i : integer;
procedure Shuma(n1,n2:number;p1,p2:integer;var s:number;var p:integer);
var shift,ndermend:integer;
Begin
shift:=1;
ndermend:=0;
while shift<=p1+1 do
Begin
s.v[shift]:=((n1.v[shift]+n2.v[shift]+ndermend)mod 10);
ndermend:=(n1.v[shift]+n2.v[shift]+ndermend) div 10;
if (shift=p1+1) and(s.v[shift]>0) then Begin p:=p1+1; exit; end;
if (shift=p1+1)and(s .v[shift]=0) then begin p:=p1; exit; end;
shift:=shift+1;
end;
end;
var sofar,r,j:integer;
Begin
dp[0].v[1]:=0;
dp[0].q:=1;
dp[1].v[1]:=1;
dp[1].q:=1;
dp[2].v[1]:=1;
dp[2].q:=1;
for i:=3 to 5000 do
Begin
shuma(dp[i-1],dp[i-2],dp[i-1].q,dp[i-2].q,dp,dp.q);
end;
while not eof(input) do
Begin
readln(input,sofar);
for j:=dp[sofar].q downto 1 do write(output,dp[sofar].v[j]);
writeln(output);
end;
end.

i wrote some debugging stiff and on the acm grader it works 0.3 when it gets to the line before while not eof(input) do

help

[subzero]

Hi

how are you??

I just tried to solve this proble... but I get Compile error, I had compiled it on Windows and Linux (Fedora) and it works fine... does any one of you knows why the online judge is saying this:

Here are the compiler error messages:

/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/std/bastring.h:
In method `class
basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > &
basic_string<char,string_char_traits<char>,__default_alloc_template<true,0>
>::replace<int>(char *, char *, int, int)':
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/std/bastring.h:229:
instantiated from here
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/std/bastring.h:453:
invalid type argument of `unary *'
/usr/local/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/../../../../include/g++-3/std/bastring.h:460:
invalid type argument of `unary *'

this is the code:

Code: Select all

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

string suma(string x, string y) {
	int n,l,res;
	x.length()>y.length() ? l=x.length() : l=y.length();
	x=string(l-x.length(),'0')+x;
	y=string(l-y.length(),'0')+y;
	string r(l,'0');
	for (l--,res=0;l>=0;l--) {
		n=x[l]+y[l]-'0'-'0'+res;
		r[l]=n%10+'0';
		res=n/10;
	}
	if(res!=0) r=string(1,res+'0')+r;
	return r;
}

int main() {
	string fib[5002];
	int i;
	fib[0]="0";
	fib[1]="1";
	fib[2]="1";
	fib[3]="2";
	fib[4]="3";
	fib[5]="5";
	for (i=6;i<5002;i++)
		fib[i]=suma(fib[i-1],fib[i-2]);
	while(scanf("%d",&i)==1){
		cout<<"The Fibonacci number for "<<i<<" is "<<fib[i]<<endl;
	}
	return 0;
}

thanks for help

[dumb dan]

The judge is using an older version of g++ (version 2.95.3).
Your error is on the line:

if(res!=0) r=string(1,res+'0')+r;

You might try replacing it with

if(res!=0) r=(char)(res+'0')+r;

[chunyi81]

It should be r = string(1,(char)(res + '0')) + r;

r is a C++ string. How can you assign a char to a string this way?

[dumb dan]

C++ is smart enough to realize there's only one sensible way to combine a char and a string and that's to treat the char as a string of size 1
Thus the two are equivalent, but I'm lazy so I prefer the shorter way of writing it.

[mersault]

Hello! I'm new here.
I try to submit 495, but get WA all the time. I've read previous posts on this problem, and checked my output. It seems OK and matches correct output that people have posted. Why do I get WA? Has it something to do with that I'm using Java? I've begun to understand that Java isn't as good to use as C/C++ here...

Code: Select all

Removed, it was accepted!