495  Fibonacci Freeze
Moderator: Board moderators

 New poster
 Posts: 37
 Joined: Fri Apr 30, 2004 6:52 pm
 Location: Portugal
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.
Any help is appreciated, thanks.
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 == m1)
sum>flag++;
}
}
void printBigInt(bigIntp big)
{
int i;
for(i = big>flag1; 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[i1],1100);
memcpy(n2, &results[i2],1100);
sumBigInt(n1,n2,sum);
for(k = sum>flag1, 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;
}
Last edited by Schutzstaffel on Thu Jan 12, 2006 6:46 pm, edited 1 time in total.
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.
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.

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

 New poster
 Posts: 37
 Joined: Fri Apr 30, 2004 6:52 pm
 Location: Portugal
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
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
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:
Try increasing the array size for the number of digits
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;

 New poster
 Posts: 37
 Joined: Fri Apr 30, 2004 6:52 pm
 Location: Portugal
I've been debugging the code now in Linux and noticed that if I precalculated 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.
Thanks for your help and for telling me the line.
Check these lines:
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.
Code: Select all
bigIntp big = malloc(sizeof(bigInt));
big>digits = malloc(sizeof(int)*size);
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.
why do i get TLE ?
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[i1],dp[i2],dp[i1].q,dp[i2].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
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[i1],dp[i2],dp[i1].q,dp[i2].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
495 Why Compile Error?
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:
thanks for help
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:
this is the code:Here are the compiler error messages:
/usr/local/lib/gcclib/i686pclinuxgnu/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/gcclib/i686pclinuxgnu/2.95.3/../../../../include/g++3/std/bastring.h:229:
instantiated from here
/usr/local/lib/gcclib/i686pclinuxgnu/2.95.3/../../../../include/g++3/std/bastring.h:453:
invalid type argument of `unary *'
/usr/local/lib/gcclib/i686pclinuxgnu/2.95.3/../../../../include/g++3/std/bastring.h:460:
invalid type argument of `unary *'
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(lx.length(),'0')+x;
y=string(ly.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[i1],fib[i2]);
while(scanf("%d",&i)==1){
cout<<"The Fibonacci number for "<<i<<" is "<<fib[i]<<endl;
}
return 0;
}
thanks for help
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.
495  WA with Java
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...
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.