495 - Fibonacci Freeze

[faisneaz]

/*fibonacci freeze*/

#include<stdio.h>
//#include<conio.h>
#include<string.h>
void add (char add1[10000],char add2[10000]);
void stcopy(char add1[10000],char add2[10000]);
void strev(char point[10000]);
void stinter(char add1[10000],char add2[10000]);
main()
{
char add1[10000],add2[10000],temp[10000],fibonaci[5000][2000];
int fibo,count,len2;
add1[0]='0';
add1[1]='\0';
add2[0]='1';
add2[1]='\0';
fibo=0;
while(fibo<50)
{
if(fibo==1)
{
stcopy(fibonaci[fibo],"0");
//printf("%s\n",fibonaci[fibo]);
//++fibo;
}
else
{
stcopy(temp,add1);
add(add1,add2);
stcopy(add2,temp);
stcopy(fibonaci[fibo],add1);
//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;
}
void stcopy(char add1[10000],char add2[10000])
{
int i;
for(i=0;add2!='\0';++i)
{
add1=add2;
}
add1='\0';
}
void add(char add1[10000],char add2[10000])
{
int a1,a2,c,k=0,i;
//char add1[1000],add2[1000];
a1=strlen(add1);
a2=strlen(add2);
if(strlen(add1)<strlen(add2))
{
stinter(add1,add2);
}
strev(add1);
strev(add2);
c=a1;
for(i=0;i<c;++i)
{
if(i<a2)
{
k=(add1-'0')+(add2-'0')+k;
add1=(k%10+'0');
k=k/10;
}
else
{
k=(add1-'0')+k;
//printf("%d",(add1-'0')+k);
add1=k%10+'0';
k=k/10;
}
}
if(k>0)
{
add1[i]=k+'0';
}
add1[i+1]='\0';
strev(add1);
strev(add2);
}
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]

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]

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]

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
		readln (a);
		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]

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]

hi...

i got TLE..

why TLE ??

anybody explains the reason ??

help me please....

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]

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

[pipo]

thanks Eduard....

I precalculated all values..

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

thanks a lot..

[Andrey]

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]

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;
}

[shamim]

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]

thanks it works.

[Jan]

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.

[smilitude]

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';
}






//code for addition 
void addition(char *first,char *second, char *answer) {
	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;
		}
		answer[i]=temp_sum+'0';
		temp_sum=0;
	}
	if(carry!=0) {
		answer[i]=carry+'0';
		answer[i+1]='\0';
	}
	else answer[i]='\0';
	
	rev(answer);
	//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++) {
			addition(sum[i-1],sum[i-2],sum[i]);
			}
	 while(scanf("%d",&num)==1) {
                printf("The Fibonacci number for %d is %s\n",num,sum[num]);

	}

	
}

[/code]

[shamim]

Code: Select all

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

Declare large arrays as global.