495 - Fibonacci Freeze

[ec3_limz]

Still got WA.... why?

I had ensured that the Fibonacci numbers can be up to 2000 digits long.

BTW, here is the updated code.

[cpp]#include <stdio.h>

int main() {
const int billion = 1000000000;
int fact[5001][200], index, start;
int i, j;

for (i = 0; i <= 5000; i++)
for (j = 0; j < 200; j++)
fact[j] = 0;

fact[0][199] = 0;
fact[1][199] = 1;
for (i = 2; i <= 5000; i++)
for (j = 199; j > 0; j++) {
if (fact[j] == 0)
break;
fact[j] = fact[j] + fact[j];
fact[j - 1] = fact[j] / billion;
fact[j] %= billion;
}

while (scanf("%d", &index) == 1) {
printf("The Fibonacci number for %d is ", index);
start = 0;
for (i = 0; i < 200; i++) {
if (start == 0 && fact[index] > 0)
start = 1;
if (start == 1) {
printf("%d", fact[index]);
start = 2;
}
else if (start > 1)
printf("%09d", fact[index][i]);
}
printf("\n");
}

return 0;
}[/cpp]

Thanks,
ec3_limz

P.S. The sample input/output for this problems are too trivial...

[Ivor]

Tell me: have you TESTED it YOURSELF???
Before posting or sending to the judge you should test it at home!

See for example the inner cycle of generation:
[c]for (j = 199; j > 0; j++)[/c]

How much sense does this line make? To me -- none at all.

Just try to debug your code, and feed it many numbers, for example:

Code: Select all

0
1
10
100
1000
4999
5000

Test it, the last one has more than thousand digits, but all you get is 5 or 6 of them.

Ivor

[mmammel]

I must have some problem reading input -- the program works fine on my PC, I checked some large values against an online fibonacci calculator. But I get "Output limit exceeded". It must get stuck in some kind of loop when it reads the input from the judge. Here is how I read:

Code: Select all

int val, i, j, nd, b, l1;
unsigned int n1[120], n2[120], c, t;
char ch[32];

do 
{ //loop
val=0;
l1=0;

gets(ch);
l1=strlen(ch);

if (l1)
{

for (i=0; i<l1; i++)
	if (ch[i]>='0' && ch[i]<='9')
		val=10*val+(int)(ch[i]-48);

 ...blah blah blah...

} //l1

} while (l1); //loop

If I add
if (val<0 || val>5000) return 1;
the same result occurs.

Thanks,
Mark

[MAXX^FACTOR]

anybody......please

tell me why it comes with "TimeLimitExceeded" ?

Code: Select all

#include <stdio.h>
#include <iostream.h>
#include <string.h>

void reverse(char *s){
	int i;
	char t[10000];
	memset(t,0,10000);
	for(i=0;i<strlen(s);i++)
		t[strlen(s)-1-i]=s[i];
	strcpy(s,t);
	return;
}

void BIGSUM(char *a,char *b){
	int i,sml,big,carry[10000]={0},temp;
	bool test;
	reverse(a);
	reverse(b);
	if(strlen(a)>=strlen(b)){
		big=strlen(a);
		sml=strlen(b);
		test=0;
	}
	else{
		big=strlen(b);
		sml=strlen(a);
		test=1;
	}
	for(i=0;i<sml;i++){
		temp=(a[i]-48)+(b[i]-48)+carry[i];
		if(temp>=10){
			a[i]=(temp-10)+48;
			carry[i+1]=1;
		}
		else
			a[i]=temp+48;
	}
	for(i=sml;i<big;i++){
		if(test==0)
			temp=(a[i]-48)+carry[i];		
		else
			temp=(b[i]-48)+carry[i];
		if(temp>=10){
			a[i]=(temp-10)+48;
			carry[i+1]=1;
		}
		else
			a[i]=temp+48;
	}
	if(carry[i]==1)
		a[i]=48+1;		
	reverse(a);
	return;
}

int main()
{
	char x[10000],y[10000],z[10000],*table[5001];
	int in,i;
		memset(x,0,10000);
		memset(y,0,10000);
		memset(z,0,10000);
		strcpy(x,"0");
		strcpy(y,"1");
		strcpy(z,"0");
		for(i=0;i<=5000-2;i++){
			BIGSUM(x,y);
			strcpy(z,x);	
			table[i+2]=new char[strlen(z)+1];
			memset(table[i+2],0,strlen(z)+1);
			strcpy(table[i+2],z);
			strcpy(x,y);
			strcpy(y,z);
		}
		while(cin>>(in)){
			if(in==0)
				cout<<"The Fibonacci number for 0 is 0"<<endl;
			else if(in==1)
				cout<<"The Fibonacci number for 1 is 1"<<endl;
			else
				cout<<"The Fibonacci number for "<<in<<" is "<<table[in]<<endl;
		}			
		return 0;
}

[Whinii F.]

I just solved this problem by using arrays, and precalculating all fibs from 0 to 5000, and then looked at the problem status..

How could Mr.Ivor solve the problem in 0.00 sec, without using any extra memory?! It looks just impossible to me.. Is it of the judge's mistake with measuring memory usages? (I experienced it some times)

thanks,

[Moinul(AUST)]

Write an effective String Addition function and you can get the 495 accepted ...


5000th Fibo is:

387896845438832563370191630832590531208212771464624510616
059721489555013904403709701082291646221066947929345285888
297381348310200895498294036143015691147893836421656394410
691021450563413370655865623825465670071252592990385493381
39288363783475189087629707120333370529231076930085180938498
018038478139967488817655546537882916442689129803846137789
690215022930824756663462249230718833248032803750391303529
033045058427011476352422702109346376991040067141748832984
228914912731040543287532980442736768229772449877498745556
919077038806370468327948113589737399931101062193081490185
708153978543791953056175107610530756887837660336673554452
588448862416192105534574936758978490279882343510235998446
639348532564119522218595630604753646454707603309024208063
825849291564528762915757591423438091423029174910889841552
098544324865940797935713168416928680395453095453886981146
650820668628974206393234384884652409887423958738019769938
203171742089322654688793640026307977800587591296713896342
142525791168727556003603113705477547246046399875880469851
78408674382863125



-Moinul

[razibcse]

My prog. always gets Compile error..

why this is happening, pls tell me someone...
I thought 5000th fibonacci number as a string coz it has 1045 digits..
so I used string addition to calculate it..
Input & output seems OK to me..

But it's not compiling to them...

What can I do?

Here's my code:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 5010
#define MAXSZ 1048

char *str_add(char fib1[],char fib2[],long len1,long len2);

char *fib[MAX];
void main()
{

long i,n,len1,len2;
char *ptr;

for(i=0;i<3;i++)
  fib[i]=(char *)malloc(3*sizeof(char));

fib[0][0]='0';
fib[0][1]='\0';
fib[1][0]='1';
fib[1][1]='\0';
fib[2][0]='1';
fib[2][1]='\0';

while(scanf("%ld",&n)==1)
  {
  for(i=3;i<=n;i++)
    {
    fib[i]=(char *)malloc(MAXSZ*sizeof(char));

    len1=strlen(fib[i-1]);
    len2=strlen(fib[i-2]);

    ptr=str_add(fib[i-1],fib[i-2],len1,len2);
    strcpy(fib[i],ptr);
    free(fib[i-3]);
    }

  printf("The Fibonacci number for %ld is %s\n",n,fib[n]);
  }
}

char *str_add(char fib1[],char fib2[],long len1,long len2)
{

long sum,max,min,dif,a,re,qu,i,j,k,x,y;
char *result;

result=(char *)malloc(MAXSZ*sizeof(char));

if(len1>=len2)
 {
 max=len1;
 min=len2;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   fib2[a+dif]=fib2[a];
   fib2[max]='\0';

 for(a=0;a<dif;a++)
   fib2[a]='0';

 }
else if(len1<len2)
 {
 max=len2;
 min=len1;
 dif=max-min;

 for(a=min-1;a>=0;a--)
   fib1[a+dif]=fib1[a];
   fib1[max]='\0';

 for(a=0;a<dif;a++)
   fib1[a]='0';

 }


qu=0;
i=MAXSZ-1;
for(a=max-1;a>=0;a--)
  {
  sum=qu+(fib1[a]-48)+(fib2[a]-48);

  if(sum>=10)
    {
    qu=sum/10;
    re=sum%10;
    }
  else if(sum<10)
    {
    qu=0;
    re=sum;
    }
  result[i--]=(char)(re+48);
  if(a==0 && qu!=0)
    {
    for(;;)
        {
        x=qu/10;
        y=qu%10;
        result[i--]=char(y+48);
        if(x==0) break;
        qu=x;
        }
    }
  }
j=i+1;
k=MAXSZ-1-j;

for(i=j;i<=MAXSZ;i++)
  result[i-j]=result[i];

result[k+1]='\0';

return result;
}

[karakX]

[quote="razibcse"]My prog. always gets Compile error..



result[i--]=char(y+48);
it is a wrong line

the correct is :
result[i--]=(char)(y+48)

but i think it is a slow algoritm, because the input is
4900
4901
...
4999

this program always counted 3 - 4900 fibonacci numbers

[razibcse]

Hi, I got it accepted...

I pointed out this line and modified the code so that first 5000 fib numbers
are generated before the input...

This is surely faster than my previous coding..

Thanx again for ur time to see my code..

Razib

[Almost Human]

Code: Select all

#include <stdio.h>

int Fibo[5001] ;

int main ( )
{
  int max = 2 , input , i ;

/*  freopen ( "495.in" , "r" , stdin ) ;
  freopen ( "495.out" , "w" , stdout ) ;*/

  Fibo[0] = 0 ; Fibo[1] = 1 ;

  while ( scanf ( "%i" , &input ) != EOF )
  {
	 if ( input >= 0 )
	 {
		printf ( "The Fibonacci number for %i is " , input ) ;

		if ( input >= max )
		{
		  for ( ; max <= input ; max ++ )
		  {
			 Fibo[max] = Fibo[max-1] + Fibo[max-2] ;
		  }
		}

		printf ( "%i\n" , Fibo[input] ) ;
	 }
  }

  return 0 ;
}

[shamim]

Try 5000 for input, you will be surprised and shocked to know how far you are from the answer. You will need to use string to generate the numbers.

[soyoja]

Hint )

5000 th fibonacci number gives 1045 digit numbers... ^^

So it's impossible to store integer variable...

I strongly recommend that you make your own Big-Integer library.

Good luck~!

[Observer]

I try to pre-calc. the first 5000th fibs. But I still get TLE......

Can anyone help me???!!!??!?!??!

[pascal]* Deleted *[/pascal]

[Zhao Le]

[cpp]#include <iostream.h>
#define Max 5000
#define Len 1045

int S[Max][Len]={0}; // Set the initial value

void CheckCarry(int n)
{
int i;
for(i=0;i<Len;i++)
while(S[n]>9)
{
S[n]-=10;
S[n][i+1]+=1;
}
}

void C(int n)
{
int i,j;
for(i=2;i<=n;i++)
{
for(j=0;j<Len;j++)
S[j]=S[i-1][j]+S[i-2][j];
CheckCarry(i);
}
}

void main()
{
int n;
S[1][0]=1; // Set the initial value
C(Max);
while(cin>>n)
{
int i,k;
cout<<"The Fibonacci number for "<<n<<" is ";
if(n==0)
cout<<"0"<<endl;
else
{
for(i=Len-1;i>=0;i--)
if(S[n])
{
k=i;
break;
}
for(i=k;i>=0;i--)
cout<<S[n];
cout<<endl;
}
}
}[/cpp]

[ezra]

if you declare your array 5000 that means the index is between 0-4999.
if the input is 5000 then your code try to read index 5000 which is illegal.
i think thats why you got RTE.