495 - Fibonacci Freeze

Moderator: Board moderators

faisneaz
New poster
Posts: 2
Joined: Tue Jun 29, 2004 7:27 pm

WHY a runtime error PLZ help 495

/*fibonacci freeze*/

#include<stdio.h>
//#include<conio.h>
#include<string.h>
void strev(char point[10000]);
main()
{
int fibo,count,len2;
fibo=0;
while(fibo<50)
{
if(fibo==1)
{
stcopy(fibonaci[fibo],"0");
//printf("%s\n",fibonaci[fibo]);
//++fibo;
}
else
{
//printf("%s\n",fibonaci[fibo]);
}
++fibo;
}
while(scanf("%d",&fibo)==1)
{
if(fibo==0)
{
printf("The Fibonacci number for 0 is 0\n");
}
else
{
printf("The Fibonacci number for %d is %s\n",fibo,fibonaci[fibo]);
}
}
return 0;
}
{
int i;
{
}
}
{
int a1,a2,c,k=0,i;
{
}
c=a1;
for(i=0;i<c;++i)
{
if(i<a2)
{
k=k/10;
}
else
{
k=k/10;
}
}
if(k>0)
{
}
}
void strev(char point[10000])
{
char temp[10000];
int j=strlen(point),i;
--j;
for(i=0;point[i]!='\0';++i)
{
temp[i]=point[j];
--j;
}
temp[i]='\0';
for(j=0;j<i;++j)
{
point[j]=temp[j];
}
point[j]='\0';
}
void stinter(char str1[10000],char str2[10000])
{
int i;
char temp[10000];
for(i=0;str1[i]!='\0';++i)
{
temp[i]=str1[i];
}
temp[i]='\0';
for(i=0;str2[i]!='\0';++i)
{
str1[i]=str2[i];
}
str1[i]='\0';
for(i=0;temp[i]!='\0';++i)
{
str2[i]=temp[i];
}
str2[i]='\0';
}

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
You need big numbers because the fib numbers get out of your type very fast !(above 94 they don`t thit in any C++/PASCAL/JAVA or other language type)

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

495 Which one is more important? Time Or Memory

I think this is not a difficult question. At first I think I could use int fibonacci[5001][1100].Its memory is too large (if n==0 fibonacci 0 is 0,it waste memory)but it works fast;So is there anyone who can tell me a better algorithm which both works fast and save memory?
Thanks!!

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

495 - TLE

I try to solve 495, but my code got TLE.
How can i optimize it?
Thanks...

Code: Select all

``````program uva495;
const
dlen = 1100;
var
f : array [0..5100,1..dlen] of byte;
s : array [0..5100] of word;
i, a, max : integer;

procedure SumLong (a, b, c : integer);
var
m, i : integer;
begin
m := s[b];
for i := dlen downto m do
begin
f[c,i] := f[c,i] + f[a,i] + f[b,i];
f[c,i-1] := f[c,i] div 10;
f[c,i] := f[c,i] mod 10;
end;
if (f[c,m-1] > 0) then s[c] := m-1 else s[c] := m;
end;

begin
fillchar(f,sizeof(f),0);
f[0,dlen] := 0;
f[1,dlen] := 1;
f[2,dlen] := 1;
s[0] := dlen;
s[1] := dlen;
s[2] := dlen;
max := 2;
while not eof(input) do
begin
if (a > max) then
begin
for i := max + 1 to a do
SumLong (i-2,i-1,i);
max := a;
end;
write ('The Fibonacci number for ',a,' is ');
for i := s[a] to dlen do write (f[a,i]);
writeln;
end;
end.``````

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:
I solved this problem with an array sized 5000*1100 and judge reported 64k memory. I believe the memory the judge reports is dynamic memory, not static.

Think of this input:

5000
5000
5000
...

It's clear it's better to memorize the outputs than to calculate them every time.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

495... TLE... T.T

hi...

i got TLE..

why TLE ??

anybody explains the reason ??

The code is....

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <ctype.h>

#define MAX	1050

void str_sum(char *min, char *max, char **ret);
char *strrev(char *str);

void main(void)
{
char a[MAX], b[MAX], v[MAX];
char *p[4];
int c;

while ( scanf("%d", &c) != -1 )
{
printf("The Fibonacci number for %d is ", c);

if ( c == 0 )
strcpy(v, "0");
else if ( c == 1 )
strcpy(v, "1");
else
{
strcpy(a, "0");
strcpy(b, "1");

c -= 1;

p[0] = a;
p[1] = b;
p[2] = v;

while ( 1 )
{
str_sum(p[0], p[1], &p[2]);			// v = a+b;
c--;

if ( c == 0 ) break;

p[3] = p[0];

p[0] = p[1];						// a = b;
p[1] = p[2];						// b = v;
p[2] = p[3];
}
}

printf("%s\n", strrev(p[2]));
}
}

void str_sum(char *min, char *max, char **ret)
{
int i;
int max_len = strlen(max);
int min_len = strlen(min);
int carry;

carry = 0;

for ( i = 0 ; i < min_len ; i++ )
{
(*ret)[i] = min[i] + max[i] - '0' + carry;

if ( (*ret)[i] > '9' )
{
carry = 1;
(*ret)[i] -= 10;
}
else
carry = 0;
}

if ( min_len ^ max_len )
carry += max[i] - '0';

if ( carry )
{
(*ret)[i] = '0' + carry;
(*ret)[i+1] = 0;
}
else
(*ret)[i] = 0;
}

char *strrev(char *str)
{
int len = strlen(str);
int i;
char ch;

for ( i = 0 ; i < len / 2 ; i++ )
{
ch = str[i];
str[i] = str[len-i-1];
str[len-i-1] = ch;
}

return str;
}
``````
Input :
5000
Output :
5000
The Fibonacci number for 5000 is 38789684543883256337019163083259053120821277146
46245106160597214895550139044037097010822916462210669479293452858882973813483102
00895498294036143015691147893836421656394410691021450563413370655865623825465670
07125259299038549338139288363783475189087629707120333370529231076930085180938498
01803847813996748881765554653788291644268912980384613778969021502293082475666346
22492307188332480328037503913035290330450584270114763524227021093463769910400671
41748832984228914912731040543287532980442736768229772449877498745556919077038806
37046832794811358973739993110106219308149018570815397854379195305617510761053075
68878376603366735544525884488624161921055345749367589784902798823435102359984466
39348532564119522218595630604753646454707603309024208063825849291564528762915757
59142343809142302917491088984155209854432486594079793571316841692868039545309545
38869811466508206686289742063932343848846524098874239587380197699382031717420893
22654688793640026307977800587591296713896342142525791168727556003603113705477547
24604639987588046985178408674382863125
is output wrong ?

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I don't look at your code carefully but for not getting TLE you must precalculate all values in the biginning of your problem.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea
thanks Eduard....

I precalculated all values..

so that the codes is very simple.. and i got AC..

thanks a lot..

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

i got TLE, why?

Code: Select all

``````#include <iostream.h>

void main()
{
int n,a[1050],b[1050],c[1050],i,s,t;
while (cin>>n)
{
for (i=1;i<1050;i++) { a[i]=0; b[i]=0; }
a[0]=1;a[1]=1;
b[0]=1;b[1]=1;
c[0]=1;c[1]=1;
if (n==0) c[1]=0;
for (t=3;t<=n;t++)
{
s=0;
c[0]=b[0];
for (i=1;i<=c[0];i++)
{
c[i]=(a[i]+b[i]+s)%10;
s=(a[i]+b[i]+s)/10;
}
if (s>0) {c[0]++;c[c[0]]=s;}
for (i=0;i<=b[0];i++) a[i]=b[i];
for (i=0;i<=c[0];i++) b[i]=c[i];
}
cout<<"The Fibonacci number for "<<n<<" is ";
for (i=c[0];i>0;i--) cout<<c[i];
cout<<endl;
}
}``````
Or other code that got Runtime error(SIGSEGV)

Code: Select all

``````#include <iostream.h>

void main()
{
const int max=5001;
int n,a[max][1050],i,t;
for (i=0;i<1050;i++) for (t=0;t<max;t++) a[t][i]=0;
a[0][0]=1;a[0][1]=0;
a[1][0]=1;a[1][1]=1;
a[2][0]=1;a[2][1]=1;
for (t=3;t<max;t++)
{
int s=0;
a[t][0]=a[t-1][0];
for (i=1;i<=a[t][0];i++)
{
a[t][i]=(a[t-1][i]+a[t-2][i]+s)%10;
s=(a[t-1][i]+a[t-2][i]+s)/10;
}
if (s>0) {a[t][0]++;a[t][a[t][0]]=s;}
}
while (cin>>n)
{
cout<<"The Fibonacci number for "<<n<<" is ";
for (i=a[n][0];i>0;i--) cout<<a[n][i];
cout<<endl;
}
}
``````
Help!

SIGWALD
New poster
Posts: 2
Joined: Wed Mar 30, 2005 8:00 pm

I haven't an error message with gcc but when i execute the program ,i have an segmentation fault.
With the bot of ACM , i have "runtime error"

i don't see the problem can you help me ?

the source is ...

#include<stdio.h>
#include<string.h>
#define BASE 10

void fibo(int tab[5010][1100])
{
int i,m,j;

memset(tab, 0,sizeof(tab));
tab [0][0] = 1;
tab [1][1] = 1;
tab [1][0] = 1;
for (i=2; i<=5000; i++)
{
m=0;
for (j=1; j<=tab[i-1][0]+1 ; j++)
{
tab[j] = tab[i-1][j]+ tab[i-2][j]+ m;
m=tab[j] / BASE;
tab[j] %= BASE;
}
tab[0] =tab [i-1][0];
if ( tab [tab [0] + 1] )
tab [0] ++;
}
}

int main()
{
int n,tab[5010][1100],i;
fibo(tab);
for( ; ; )
{
if(scanf("%d",&n)==EOF) break;
printf ("The Fibonacci number for %d is ", n);
for (i = tab[n][0]; i >= 1; i--)
printf ("%d", tab [n]);
printf("\n");
}
return 0;
}
SIGWALD

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
int n,tab[5010][1100],i;
You can not declare large arrays as local to any function, including main.

Either declare them as global or declare them as static.

SIGWALD
New poster
Posts: 2
Joined: Wed Mar 30, 2005 8:00 pm

thx

thanks it works.
SIGWALD

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Your first code gets TLE because if the input is 5000, the program calculates all the fibonacci numbers from 1 to 5000. If you give 5000 again the code again calculates all.

Your second code gets runtime error because you are declaring a array locally. And it has 5000*1050 elements. Which is quite big. So, use it as global. And there is another facility. You don't have to initialize it.
Ami ekhono shopno dekhi...
HomePage

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

495 RE!!! [ i hate RE]

hmm.... here is the code...
i dont know, what s wrong...
you might know...
so, if you know, please let me know...
you know, i'll be really greatful!
[a lot of no! ]

Code: Select all

``````/*
495 fibonacci freezes
submission 1 TLE 2 WA 3 RE
coded at 3:26 am on 13th oct

after the tle i changed the code, used memory
i hate runtime error!!
*/

#include <stdio.h>
#include <string.h>
#define MAX 2000

//code for reversing
void rev(char *num){
long len,i;
char ch;
len=strlen(num);
for(i=0;i<len/2;i++) {
ch=num[i];
num[i]=num[len-1-i];
num[len-1-i] = ch;
}
}

//code for zero justify
void zero_justify(char *array,long n) {
long i;
long len;
len=strlen(array);
for(i=len;i<len+n;i++)
array[i]='0';
array[len+n]='\0';
}

long x,y;
long i;
char backup1[MAX+1],backup2[MAX+1];
char carry,temp_sum;

//i dont want to destroy the data, cause i'll use them later!
strcpy(backup1,first);
strcpy(backup2,second);

x=strlen(first);
y=strlen(second);

//to always keep first bigger - "hold_me_for_a_while" ;=)
if(x<y) {
auto char hold_me_for_a_while[MAX+1];
strcpy(hold_me_for_a_while,first);
strcpy(first,second);
strcpy(second,hold_me_for_a_while);
i=x;
x=y;
y=i;
}

rev(first);
rev(second);

zero_justify(second,x-y);

carry=0;
for(i=0;i<x;i++) {
temp_sum=first[i]-'0'+second[i]-'0'+carry;
carry=0;
if(temp_sum>9) {
carry=(char)(temp_sum-temp_sum%10)/10;
temp_sum=temp_sum%10;
}
temp_sum=0;
}
if(carry!=0) {
}

//i kept my promise! ;-)
strcpy(first,backup1);
strcpy(second,backup2);

}

void main() {
int num,i;
char sum[5001][MAX+1];

strcpy(sum[0],"0");
strcpy(sum[1],"1");
strcpy(sum[2],"1");
for(i=3;i<=5000;i++) {
}
while(scanf("%d",&num)==1) {
printf("The Fibonacci number for %d is %s\n",num,sum[num]);

}

}

``````
[/code]
fahim
#include <smile.h>

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Code: Select all

``````void main() {
int num,i;
char sum[5001][MAX+1];

strcpy(sum[0],"0");``````
Declare large arrays as global.