495 - Fibonacci Freeze

ankur_vjy · Post by **ankur_vjy** » Thu Jan 24, 2008 8:56 pm

i keep getting compilation error. where am i wrong ?

#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

#define MAX 1500

class BigInt {
	string str;
	int sign;
	int len;
public:
	BigInt(BigInt &b) {
		str.resize(MAX);
		fill(str.begin(),str.end(),'0');
		str=b.str;
		sign=b.sign;
		len=b.len;
	}
	BigInt(string s) {
		sign='+';
		str.resize(MAX);
		fill(str.begin(),str.end(),'0');
		if(s[0]=='-') {
			sign='-';
			s[0]='0';
		}
		copy_backward(s.begin(),s.end(),str.end());
		len=s.length();
	}
	BigInt() {
		sign='+';
		str.resize(MAX);
		fill(str.begin(),str.end(),'0');
		len=0;
	}

	BigInt operator+(BigInt B) {
		BigInt sum;
		int big=(len>B.len?len : B.len);
		int stop=MAX-big;
		int carry=0;
		for(int i=MAX-1;i>=stop-1;i--) {
			sum.str[i]=carry + str[i]+B.str[i] - 2*'0';
			carry=sum.str[i]/10;
			sum.str[i]%=10;
			sum.str[i]+='0';
		}
		if(sum.str[stop-1]!='0')
			sum.len=big+1;
		else
			sum.len=big;
		return sum;

	}
	void calclen() {
		int i=0;
		for(i=0;str[i]=='0';i++);
		len=MAX-i;
	}
	BigInt operator-(BigInt B) {
		BigInt sum;
		for(int i=MAX-len;i<MAX;i++)
			B.str[i]='9'-B.str[i]+'0';
		B=B+BigInt("1");
		sum=*this+B;
		if(sum.len>this->len) {
			sum.str[MAX-sum.len]='0';
			sum.len--;
		}
		sum.calclen();
		return sum;

	}

	BigInt operator++() {
		(*this)=(*this)+BigInt("1");
		calclen();
	}


	BigInt operator*(BigInt B) {
		BigInt prod;
		for(int j=MAX-1;j>=MAX-len;j--) 
			prod=prod+multiply(*this,B.str[j],MAX-j-1);
		prod.calclen();
		return prod;
	}
	BigInt multiply(BigInt B, char c, int shift) {
		BigInt term;
		int carry=0;
		for(int i=MAX-1;i>=MAX-B.len -1;i--) {
			term.str[i-shift]=((B.str[i]-'0')*(c-'0') + carry)%10 + '0';
			carry=((B.str[i]-'0')*(c-'0') + carry)/10;
		}
		term.calclen();
		return term;
	}
	friend ostream& operator<<(ostream &stream, BigInt B);
};

ostream& operator<<(ostream &stream, BigInt B) {
	if(B.len==0)
		stream<<'0';
	for(int i=B.str.size()-B.len;i<B.str.size();i++)
		stream<<B.str[i];
	return stream;
}

int main() {
	int n;
	while(true) {
		cin>>n;
		if(feof(stdin))
			break;		
		BigInt last("1"),sLast("0");
		for(int i=0;i<n-1;i++) {
			BigInt temp=last;
			last=last+sLast;
			sLast=temp;
		}
		if(n==0)
			last=BigInt("0");
		cout<<"The Fibonacci number for "<<n<<" is "<<last<<"\n";
	}
	return 0;
}

[/code]

Jan · Post by **Jan** » Fri Jan 25, 2008 7:40 pm

I got the following message

Code: Select all

 In member function `BigInt BigInt::operator-(BigInt)':
66: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
   std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
66:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'
 In member function `BigInt BigInt::operator++()':
78: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
   std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
78:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'
 In member function `BigInt BigInt::operator*(BigInt)':
86: no matching function for call to `BigInt::BigInt(BigInt)'
21: candidates are: BigInt::BigInt(std::basic_string<char,
   std::char_traits<char>, std::allocator<char> >)
14:                 BigInt::BigInt(BigInt&)
86:   initializing argument 1 of `BigInt BigInt::operator+(BigInt)'

Try erasing/commenting the following method - 'BigInt(BigInt &b)'.

turcse143 · Post by **turcse143** » Wed Feb 27, 2008 9:32 pm

---u can use 2D array for generate the
Fibonacci number.
---every row index denotes the nth Fibonacci number
---just add the previous value and set the next array.
it is fasted &easily implemented.

abid_iut · Post by **abid_iut** » Wed Jul 16, 2008 7:48 am

waht data type should i use for 5000th fibonacci number??
for problem 495:
ne one give me some tricky input???

sapnil · Post by **sapnil** » Thu Jul 17, 2008 12:28 am

There is no special input.
>> use simple string addition.

plz post in right place

Thanks
Sapnil

mesba_iutoic · Post by **mesba_iutoic** » Sat Jul 19, 2008 11:32 pm

You hav to do the string operation,

simply bcoz there's no data type who can take more than 1000 digits.

vinitadroit · Post by **vinitadroit** » Fri Oct 03, 2008 10:50 am

plz .. check where' s the mistake
code is in c++ :
plz reply soon i m nw in uva already frustrated...

#include<iostream>
using namespace std;
int b[5001][1200]={0};
int arr[5001][1200];
void reverse(int a[][1200],int n)
{
int i=0,j;
while(a[n]!=-1) i++;
for(j=0;j<=i-1;j++) b[n][j]=a[n][i-j-1];
for(j=0;j<=i-1;j++) a[n][j]=b[n][j];
}
int main()
{

int k,z,j,i,sum,num,temp;
for(int y=1;y<5001;y++)
for(int m=0;m<1200;m++)
arr[y][m]=-1;
arr[0][0]=0;
arr[1][0]=1;
arr[2][0]=1;
for(i=3;i<5001;i++)
{
z=k=j=0;
while(arr[i-2][j]!=-1) j++;j--;
while(arr[i-1][k]!=-1) k++;k--;
while(j>=0)
{
sum=0;
sum+=arr[i-1][k]+arr[i-2][j];
j--;k--;
arr[z]=sum%10;
z++;
while(sum>=10)
{
sum/=10;
if(k>=0 && j>=0)
{sum=sum+arr[i-1][k]+arr[i-2][j];temp=sum%10;
arr[z]=temp;k--;j--;
}//if
else if(k<0) arr[z]=sum;
else if(k>=0 && j<0) {sum=sum+arr[i-1][k];
arr[z]=sum%10;k--;
}//if
z++;
}//while
if(k>=0) arr[z]=arr[i-1][k];
}
reverse(arr,i);
}
while(cin>>num)
{ i=0;
cout<<"The Fibonacci number for "<<num<<" is ";
while(arr[num]!=-1)
{
cout<<arr[num];i++;
}
cout<<endl;
}
return 0;
}

Skorpio · Post by **Skorpio** » Wed Aug 05, 2009 7:04 pm

Can anybody tell me, how can I get rid if time limit exceed about this problem ??
This is my code..

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

char res[2500];

int toint(char ch)
{
return (ch-'0');
}
char tochar(int c)
{
return (c+'0');
}

void reverse(char s[])
{
int i,j;

for(i=0,j=strlen(s)-1;i<j;i++,j--)
{
s^=s[j]^=s^=s[j];
}
}

void addstr(char s[],char t[],char add[])
{
int carry,i,j,k;
long temp,temp1,temp2;
char result[1001];

carry=0;
k=0;
for(i=strlen(s)-1,j=strlen(t)-1;i>=0 || j>=0;i--,j--,k++)
{
temp1=temp2=0;
if(i>=0)
temp1=toint(s);
if(j>=0)
temp2=toint(t[j]);
temp=temp1+temp2;
result[k]=tochar((temp+carry)%10);
carry=(carry+temp)/10;
}
while(carry!=0)
{
result[k++]=tochar(carry%10);
carry/=10;
}
result[k]='\0';
reverse(result);
strcpy(add,result);
}

void bigFib(long n,char res[2500])
{
char f[2000],s[2000];
long i;

f[0]='1';
f[1]='\0';
s[0]='1';
s[1]='\0';

if(n==0)
{
res[0]='0';
res[1]='\0';
}
else if(n==1 || n==2)
{
res[0]='1';
res[1]='\0';
}
else if(n>2)
{
for(i=3;i<=n;i++)
{
addstr(f,s,res);
strcpy(f,s);
strcpy(s,res);
}
}
}

int main(void)
{
long n;

while(scanf("%ld",&n)!=EOF)
{
bigFib(n,res);
printf("The Fibonacci number for %ld is %s\n",n,res);
}
return 0;
}

ksc91u · Post by **ksc91u** » Mon Nov 02, 2009 11:41 am

http://github.com/ksc91u/fibonacci_free ... bfast.java

Could not find what wrong with this.
Wrong answer.

I can compute fib 5000 = 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

38789684543883256....4382863125

MIN MAINO · Post by **MIN MAINO** » Wed Sep 01, 2010 2:23 pm

#include<stdio.h>
//#include<conio.h>
#define max 5000

long long d[max+1]={0};

long long fib_frz()
{
register int a;
d[0]=0;
d[1]=1;
for(a=2;a<=max;a++)
d[a]=d[a-1]+d[a-2];
return 0;
}
int main()
{
int f;
//clrscr();
fib_frz();
//freopen("in495.txt","r",stdin);
while(scanf("%d",&f)!=EOF)
printf("The Fibonacci number for %d is %lld\n",f,d[f]);
return 0;
}

MIN MAINO · Post by **MIN MAINO** » Fri Sep 03, 2010 11:33 am

#include<stdio.h>
//#include<conio.h>
#define max 5000

long long d[max+1]={0};

long long fib_frz()
{
register int a;
d[0]=0;
d[1]=1;
for(a=2;a<=max;a++)
d[a]=d[a-1]+d[a-2];
return 0;
}
int main()
{
int f;
//clrscr();
fib_frz();
//freopen("in495.txt","r",stdin);
while(scanf("%d",&f)!=EOF)
printf("The Fibonacci number for %d is %lld\n",f,d[f]);
return 0;
}

sazzadcsedu · Post by **sazzadcsedu** » Sat Sep 04, 2010 5:32 pm

Code: Select all

input :
5000

Output:
 
The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

So you must use BigInteger to solve this problem.

noor_aub · Post by **noor_aub** » Wed Nov 03, 2010 4:32 pm

What Should I Do. I am getting R/E

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
	//freopen("in.txt","r",stdin);
	int ind_print=3,cas=5000,p=1;
	char re[10]={'0','1','2','3','4','5','6','7','8','9'};
	char aa[]={'1'};	
	char str1[2000],str2[2000],sum[2000],str3[2000],bigstr[2000],smallstr[2000],print[5001][2000];
	memset(print[0],0x0,sizeof(print[0])); 
	memset(print[1],0x0,sizeof(print[1])); 
	memset(print[2],0x0,sizeof(print[2])); 
	memset(str2,0x0,sizeof(str2)); 
	memset(str3,0x0,sizeof(str3)); 
	memset(bigstr,0x0,sizeof(bigstr)); 
	memset(smallstr,0x0,sizeof(smallstr)); 
	strcpy(str1,aa);
	strcpy(str2,aa);
	while(1)
	{
		//cout<<endl<<bigstr<<' '<<smallstr<<endl;
		int len1,len2,big,small,ind,def,temp,temp2,sum_ind,cnt,flag,ind_str2;
		len1=len2=big=small=ind=def=temp=sum_ind=cnt=temp2=flag=ind_str2=0;
		len1=strlen(str1);
		len2=strlen(str2);
		if(len1>len2)
		{
				big=len1;
				small=len2;
				def=big-small;
				strcpy(bigstr,str1);
				for(ind=big-1;ind>=def;ind--)
				{
						smallstr[ind]=str2[small-1];
						small--;
				}
				small=len2;
		}
		else if(len1<len2)
		{
				big=len2;
				small=len1;
				def=big-small;
				strcpy(bigstr,str2);
				for(ind=big-1;ind>=def;ind--)
				{
						smallstr[ind]=str1[small-1];	
						small--;
				}
				small=len1;
		}
		else/*If Two Number Are in Same Leangth*/
		{
				big=len2;
				small=len1;
				strcpy(bigstr,str2);
				strcpy(smallstr,str1);
				flag=1;
		}
		for(sum_ind=2000-1;;sum_ind--)
		{
				cnt++;
				temp2=(((int)bigstr[big-1])-48)+(((int)smallstr[big-1])-48)+temp;
				if(temp2>9)
				{
						int H=temp2%10;
						sum[sum_ind]=re[H];
						temp=1;
				}
				else
				{
						sum[sum_ind]=re[temp2];
						temp=0;
				}
				big--;
				if(cnt==small)
				{
					if(!flag)
						sum_ind--;
					break;
				}
		}
		if(!flag)/*If Two Number Are in Same Leangth Then No Need to Add Second Time */
		{
			for(;;sum_ind--)
			{
					cnt++;
					temp2=(((int)bigstr[big-1])-48)+temp;
					if(temp2>9)
					{
							int H=temp2%10;
							sum[sum_ind]=re[H];
							temp=1;
					}
					else
					{
							sum[sum_ind]=re[temp2];
							temp=0;
					}
					big--;
					if(big==0)
						break;
			}
		}
		if(temp==1)
		{
			sum[sum_ind-1]='1';
			cnt++;
		}
		strcpy(str1,str2);
		for(int f=2000-cnt;f<2000;f++)
		{
			str3[ind_str2]=sum[f];
			ind_str2++;
		}
		strcpy(str2,str3);
		strcpy(print[ind_print],str3);
		ind_print++;
		cas--;
		if(cas==2)
		{
				//printf("%s\n",str2);
				break;
		}
		p=0;
	}
	int inp;
	while(scanf("%d",&inp)==1)
	{
		int cas=inp;
		if(cas>2)
			printf("The Fibonacci number for %d is %s\n",cas,print[cas]);
		else if(cas==1||cas==2)
			printf("The Fibonacci number for %d is %d\n",cas,1);
		else
			printf("The Fibonacci number for %d is %d\n",cas,0);
	}
	return 0;
}

slash190 · Post by **slash190** » Wed Feb 16, 2011 8:07 pm

if everything is right still getting WA
try making the array size 10000 instead of 5002

wawa · Post by **wawa** » Thu Mar 31, 2011 3:07 pm

Code: Select all

#include <iostream>
#include <string>
using namespace std;
string strAdd (string m, string n)
{
	string result;
	int addition;
	int stack = 0;
	if (m.size() >= n.size())
	{
		if (m.size() > n.size())
			n = "0" + n;
		for (int i = n.size() - 1; i >= 0; i--)
		{
			if (stack != 0)
			{
				addition = int(m[i]) + int(n[i]) - 47;
				stack = 0;
			}
			else
				addition = int(m[i]) + int(n[i]) - 48;
			if (addition > 57)
			{
				addition -= 10;
				stack++;
			}
			result = char (addition) + result;
		}
		if (stack != 0)
			result = "1" + result;
	}
	else
		return strAdd (n, m);
	return result;
}
int main()
{
	string fibbo[5001];
	fibbo[0] = "0";
	fibbo[1] = "1";
	for (int i = 2; i < 5001; i++)
		fibbo[i] = strAdd (fibbo[i-1], fibbo[i-2]);
	int n;
	while (scanf("%d", &n) == 1)
	{
		cout << "The Fibonacci number for " << n << " is " << fibbo[n] << endl;
	}
	return 0;
}

I used string to get the BigNum...
It s successful at ideone.com....
but, i got CE in UVA......
help me, pls...X(

OJ Board

495 - Fibonacci Freeze

495 need input

Re: 495 need input

Re: 495 need input

495:fibonacci freeze ..... getting WA as verdict

495 :How can I get rid of Time limit exceed ???

Re: 495 - Fibonacci Freeze

what is the problem in belows Code...495_Fib_Fiz?

[495] Fibonacci freez

Re: what is the problem in belows Code...495_Fib_Fiz?

Re: 495 - Fibonacci Freeze

Re: 495 Why WA??

495 - Fibonacct Freeze ---- Compilation error..!!!