495 - Fibonacci Freeze

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Nov 28, 2005 11:09 am

man, you are awesome!
thanks a lot!
fahim
#include <smile.h>

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel » Thu Jan 12, 2006 3:11 pm

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.
Last edited by Schutzstaffel on Thu Jan 12, 2006 6:46 pm, edited 1 time in total.
Image

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Jan 12, 2006 5:02 pm

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
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel » Thu Jan 12, 2006 6:51 pm

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.
Image

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Jan 12, 2006 7:18 pm

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.
fahim
#include <smile.h>

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel » Thu Jan 12, 2006 8:39 pm

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
Image

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Jan 13, 2006 5:23 am

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
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel » Sat Jan 14, 2006 5:39 am

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.
Image

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sat Jan 14, 2006 9:21 am

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
New poster
Posts: 3
Joined: Mon Mar 06, 2006 5:48 pm

why do i get TLE ?

Post by poti » Sat Mar 11, 2006 5:16 pm

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
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

495 Why Compile Error?

Post by subzero » Sat May 27, 2006 10:49 pm

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 :wink:
Last edited by subzero on Tue May 30, 2006 7:23 pm, edited 1 time in total.
There is no knowledge that is no power.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Mon May 29, 2006 5:03 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon May 29, 2006 5:10 pm

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?

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Mon May 29, 2006 6:28 pm

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
New poster
Posts: 4
Joined: Tue May 30, 2006 3:03 pm

495 - WA with Java

Post by mersault » Tue May 30, 2006 3:11 pm

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!
Last edited by mersault on Tue May 30, 2006 11:37 pm, edited 1 time in total.

Post Reply

Return to “Volume 4 (400-499)”