495 - Fibonacci Freeze

[shamim]

Eventhough you have precalclulated the result, still the precalclulation time is very long. I ran your code in my pc and it got stucked in the precalculation function. I never got an opportunity to give input.

[rlatif119]

I've found the problem. The outer loop
for(n=2;n<=5000;++n) at module calculate_and_store is totally unnecessary. I GOT AC
Thanks anyway Shamim for you reply

[if11026]

Why does my code produce WA ?

Code: Select all

#include <sys/types.h> 
#include <sys/stat.h> 
#include <fcntl.h> 
#include <stdio.h> 
              



long double FibTab[5000];
void Fib(long n)
{
	long i,j;
	FibTab[0] = 0;
	FibTab[1] = 1;
	
	
	for( i = 2; i <= n; i++)
	{
		FibTab[i] = FibTab[i-1] + FibTab[i-2];
	}


}


int main()
{
	

	/*#ifndef ONLINE_JUDGE 
 	 close (0); open ("myprog.in", O_RDONLY); 
 	 close (1); open ("myprog.out", O_WRONLY | O_CREAT,0600); 
	#endif 	*/
	
	long i;
	Fib(5000);
	
	while (scanf("%ld",&i) != -1)
	{
		printf("The Fibonacci number for %ld is %0.Lf\n",i,FibTab[i]);
	}

	
	return 0;	
}

[c][/c]

[Md. Azam Khan]

Hi,
Do you know 1500th fibonacci number more than 1000 digit! and how much digit contain in Long double range? Is it possible to solve this problem without string processing? Though i didn't solve this problem yet, i think this suggesstion will help you. With best wishes.

I born to code

[wyanez]

I got accepted using BigInt (C and Java 1.332 seconds) with a array of 1050 digits!.

Good Luck!

[Minilek]

When you say you used BigInt for java, you mean java.math.BigInteger? I thought we can't use the java.math library for ACM?

[Heartattack!]

I found this way of solving the problem without using strings. It produces the SAME output for ALL inputs as the one my friend got AC with. My program runs 0.477 secs and gives WA. WHY???? Can anyone help? I know the algo sucks....memory & timewise, but i didn't want strings. Could someone help me?

Code: Select all

[cpp]
#include "iostream"
#define BASE 10000

using namespace std;
class bigint
{
public:

	int place[263];
	bigint()
	{
		for(int i=0;i<262;i++)
			place[i]=0;
	};
};

bigint fib[5002];

/*Got AC. Taking out the all important output() function.

void main(void)
{
	register int i,j;

	fib[1].place[0]=1;

	for(i=2;i<5002;i++)
		for(j=0;j<263;j++)
		{
			fib[i].place[j]+=fib[i-1].place[j]+fib[i-2].place[j];
			if(fib[i].place[j]>BASE)
			{
				fib[i].place[j+1]++;
				fib[i].place[j]-=BASE;
			}
		}

	while(cin>>i)
	{
		if(i==0)
			cout<<"The Fibonacci number for 0 is 0"<<endl;
		else
			output(i);
	}


}
[/cpp]

[Heartattack!]

I found this way of solving the problem without using strings. It produces the SAME output for ALL inputs as the one my friend got AC with. My program runs 0.477 secs and gives WA. WHY???? Can anyone help? I know the algo sucks....memory & timewise, but i didn't want strings. Could someone help me?

Code:
[cpp]
#include "iostream"
#define BASE 10000

using namespace std;
class bigint
{
public:

int place[263];
bigint()
{
for(int i=0;i<262;i++)
place=0;
};
};

bigint fib[5002];


void output(int index)
{
register int i;
bool flag=false;
for(i=262;fib[index].place==0;i--)
;
cout<<"The Fibonacci number for "<<index<<" is ";

while(i)
{
if(flag)
{
if(fib[index].place<10)
cout<<(int)0;
if(fib[index].place<100)
cout<<(int)0;
if(fib[index].place<1000)
cout<<(int)0;
}
cout<<fib[index].place;
i--;
flag=true;
}
cout<<fib[index].place[0]<<endl;
}


void main(void)
{
register int i,j;

fib[1].place[0]=1;

for(i=2;i<5002;i++)
for(j=0;j<263;j++)
{
fib.place[j]+=fib[i-1].place[j]+fib[i-2].place[j];
if(fib.place[j]>BASE)
{
fib.place[j+1]++;
fib.place[j]-=BASE;
}
}

while(cin>>i)
{
if(i==0)
cout<<"The Fibonacci number for 0 is 0"<<endl;
else
output(i);
}


}
[/cpp]


_________________

[Heartattack!]

I wrote this code to solve the problem without strings. It works fine on my pc generating the correct output for all test cases as compared to the stringed program that got AC. However, the judge says WA. Can anyone help? Pretty please!

Code: Select all

[cpp]
#include "iostream"
#define BASE 10000

using namespace std;
class bigint
{
public:

	int place[263];
	bigint()
	{
		for(int i=0;i<262;i++)
			place[i]=0;
	};
};

bigint fib[5002];


/*Got AC 8) . Still, just taking out the output() function. That's the most important!!*/
void main(void)
{
	register int i,j;

	fib[1].place[0]=1;

	for(i=2;i<5002;i++)
		for(j=0;j<263;j++)
		{
			fib[i].place[j]+=fib[i-1].place[j]+fib[i-2].place[j];
			if(fib[i].place[j]>BASE)
			{
				fib[i].place[j+1]++;
				fib[i].place[j]-=BASE;
			}
		}

	while(cin>>i)
	{
		if(i==0)
			cout<<"The Fibonacci number for 0 is 0"<<endl;
		else
			output(i);
	}


}
[/cpp]

[Piotrek Mazur]

I wrote this code to solve the problem without strings. It works fine on my pc generating the correct output for all test cases as compared to the stringed program that got AC. However, the judge says WA. Can anyone help? Pretty please!

Maybe your problem is in function main() - it has wrong type and I think it's returning wrong exit code. You should write sth like that:
[c]int main()
{
/* your code */
return 0;
}[/c]
Program exit code different from 0 can have WA.

[Heartattack!]

Nah, the program produced almost the same output. I had checked it manually before and got nothing, so I wrote a file compare program and got 5 differences. All related to 0 in some form. I corrected it and got AC.
I was wrong about another thing, too. My string code used 3064 kb of mem and 0.344 seconds. My int array used a hell of a lot more mem:5584kb but got there in 0.477 secs. I thought it'd take ages longer. Besides, this was an experiment. If I'd used arrays of 64 bit ints rather than the normal ones, I could make the base 10^19 instead of 10^4. That would reduce the computations needed by a great deal. So, the algo's pretty time efficient when using bigger bases. Maybe I'll try it after my exams!
Thanks anyway Piotrek. Hope we can help each other again someday.

[Morning]

the BigInteger class is copied from others,it should be work properly,but why i'd get a MLE???
this code can get AC when solving the 10579 problem which n is from 1 to 1000,and only used 64 memory
[cpp]
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <malloc.h>
#include <cmath>
#include <cstring>
#include <ctime>
#include <strstream>
#include <string>
#include <stdexcept>

using namespace std;
/***************************************************************************
main.cpp - description
-------------------
begin : Thu Aug 29 02:15:55 BDT 2002
copyright : (C) 2002 by Mahbub Murshed Suman
email : suman@bttb.net.bd
***************************************************************************/
/**
* BigInteger Class
* Version 6.7.28
* Last Updated: July 30, 2004
*
* Copyright (c) 2001
* S. M. Mahbub Murshed Suman (udvranto@yahoo.com)
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. S. M. Mahbub Murshed Suman makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/

namespace BigMath
{
enum BigMathERROR { BigMathMEM = 1 , BigMathOVERFLOW , BigMathUNDERFLOW, BigMathINVALIDINTEGER, BigMathDIVIDEBYZERO,BigMathDomain};

const char *BigIntErrDes[] = { "Allocation Failed", "Overflow","Underflow", "Invalid Integer", "Divide by Zero" ,"Domain Error", NULL};
const char BigIntPROGRAMNAME[] = { "BigInteger" };
const int BigIntMajorVersion = 6;
const int BigIntMinorVersion = 7;
const int BigIntRevision = 28;
const char LastUpdated[] = {"July 30, 2004"};
const char AuthorName[] = {"S. M. Mahbub Murshed Suman"};
const char *AuthorEmail[] = {"udvranto@yahoo.com","suman@bttb.net.bd", NULL};

void Dump(const char *,enum BigMathERROR);
string& DumpString (char const*,enum BigMathERROR);

// The Size Type
typedef unsigned int SizeT;
// The Data Type
typedef unsigned int DATATYPE;

// The Base Used
const DATATYPE BASE = 10000;
// An invalid data
const DATATYPE INVALIDDATA = 65535U;
// Number of digits in `BASE'
const SizeT LOG10BASE = 4;
class BigInteger
{
private:
// The integer array to hold the number
DATATYPE *TheNumber;
// Start of the location of the number in the array
SizeT Start;
// End of the location of the number in the array
SizeT End;
// True if the number is negative
bool isNegative;

// Constructor with specified bytes
BigInteger(SizeT,DATATYPE,bool);

// Copies data to 'this' upto size bytes
void datacopy(BigInteger const&,SizeT);

// Determines valid data range
SizeT datalen(DATATYPE const*) const;
// deallocates the array
void deallocateBigInteger();
// Trims zeros in front of a number
void TrimZeros();
// the array with the `fill' value
void Set(DATATYPE);

// Subscript operator
DATATYPE& operator[](unsigned int) const;
public:
// Default Constructor
BigInteger();
// Long integer constructor
BigInteger(long);
// Character array constructor
BigInteger(char const*);
// Copy Constructor
BigInteger(BigInteger const&);

// The Destructor
~BigInteger();

// Compares Two BigInteger values irrespective of sign
int UnsignedCompareTo(BigInteger const&)const;
// Compares Two BigInteger values
int CompareTo(BigInteger const&)const;

// Returns Number of digits in the BigInteger
SizeT Digits() const;
// Determines if the number representation is OK or not
bool isValidNumber() const;
// True is the nubmer is zero
bool isZero()const;

// Straight pen-pencil implementation for addition
BigInteger& Add(BigInteger const&) const;
// Straight pen-pencil implementation for subtraction
BigInteger& Subtract(BigInteger const&) const;
// Straight pen-pencil implementation for multiplication
BigInteger& Multiply(BigInteger const&) const;
BigInteger& Multiply(DATATYPE const&) const;
// Straight pen-pencil implementation for division and remainder
BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const;
BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) const;

// Overloaded Binary Operators

// Adds Two BigInteger
friend BigInteger& operator+(BigInteger const&, BigInteger const&);
// Subtructs Two BigInteger
friend BigInteger& operator-(BigInteger const&, BigInteger const&);
// Multiplies Two BigInteger
friend BigInteger& operator*(BigInteger const&, BigInteger const&);
friend BigInteger& operator*(BigInteger const&, DATATYPE const&);
friend BigInteger& operator*(DATATYPE const&, BigInteger const&);
// Divides Two BigInteger
friend BigInteger& DivideAndRemainder(BigInteger const&, BigInteger const&,BigInteger&,bool);
friend BigInteger& DivideAndRemainder(BigInteger const&, DATATYPE const&,DATATYPE&,bool);
friend BigInteger& operator/(BigInteger const&, BigInteger const&);
friend BigInteger& operator/(BigInteger const&, DATATYPE const&);
friend BigInteger& operator/(DATATYPE const&, BigInteger const&);
// Modulo Division of Two BigInteger
friend BigInteger& operator%(BigInteger const&, BigInteger const&);
friend BigInteger& operator%(BigInteger const&, DATATYPE const&);
friend BigInteger& operator%(DATATYPE const&, BigInteger const&);

// Assignment Operator
BigInteger& operator=(BigInteger const&);

// Inserter
friend ostream& operator<<(ostream& , BigInteger const&);
// Extractor
friend istream& operator>>(istream& , BigInteger& );

// Overloaded Unary Operators

// Postfix Unary Increment
BigInteger& operator++();
// Prefix Unary Increment
BigInteger& operator++(int);

// Postfix Unary Decrement
BigInteger& operator--();
// Prefix Unary Decrement
BigInteger& operator--(int);

// Negation
BigInteger& operator-();

// Bit Wise Operators

// Left Shift
BigInteger& operator<<(SizeT);
// Right Shift
BigInteger& operator>>(SizeT);
// Returns the BigInteger absolute
void abs();
friend BigInteger& abs(BigInteger&);

// Conversion functions
string& toString() const;
int toInt();
long toLong();

// Others
BigInteger& Power(long )const;
BigInteger& OldSquareRoot() const;
BigInteger& SquareRoot() const;
};

// Private Constructor which provides a new BigInteger Object
// Filled with specified data
// Useful for internal operation
BigInteger::BigInteger(SizeT bytes,DATATYPE fill, bool toInit = true)
{
TheNumber = new DATATYPE[bytes];
isNegative = false;
Start = 0;
End = bytes - 1;

if(toInit) Set(fill);
}

// Default Constructor
BigInteger::BigInteger()
{
TheNumber = new DATATYPE[1];
TheNumber[0] = 0;
Start = 0;
End = 0;
isNegative = false;
}

// Long Constructor
BigInteger::BigInteger(long n)
{
if(n<0)
{
isNegative = true;
n *= -1;
}
else isNegative = false;

SizeT i = (SizeT)(floor(log10((double)n)/LOG10BASE) + 1);

Start = 0;
End = i-1;
TheNumber = new DATATYPE ;
Set(0);

while(n)
{
TheNumber[--i] = n % BASE;
n /= BASE;
}
TrimZeros();
}

// Character array constructor
BigInteger::BigInteger(char const* n)
{
if(n[0]=='-') { isNegative = true; n++; }
else if(n[0]=='+') { isNegative = false; n++; }
else isNegative = false;

while(*n=='0') n++;

int l = strlen(n);
if(l==0)
{
*this = *new BigInteger();
return;
}
Start = 0;
End = (SizeT)(l/LOG10BASE + l%LOG10BASE - 1);
TheNumber = new DATATYPE [Digits()];
Set(0);

int cur = l - 1;
for(SizeT i = End; i>=Start;i--)
{
if(cur<0) break;
DATATYPE r = 0;
DATATYPE TEN = 1;
for(l=0;l<4;l++)
{
if(cur<0) break;
r = r + TEN*(n[cur]-'0');
TEN *= 10;
cur--;
}
TheNumber = r;
}
TrimZeros();
if(isZero()) isNegative = false;
}

// Copy constructor
BigInteger::BigInteger(BigInteger const& Temp)
{
Start = 0;
End = Temp.Digits() - 1;
TheNumber = new DATATYPE [Temp.Digits()];

datacopy(Temp,Temp.Digits());
isNegative = Temp.isNegative;
}

// Deallocates the array
void BigInteger::deallocateBigInteger()
{
if(TheNumber!=0)
{
delete [] TheNumber;
TheNumber = 0;
}
}

// The Destructor
BigInteger::~BigInteger()
{
deallocateBigInteger();
Start = 0;
End = 0;
}

// Sets the array with the `fill' value
void BigInteger::Set(DATATYPE fill)
{
for(SizeT i=Start;i<=End;i++)
TheNumber = fill;
}

// Copies data from `a' to `this'
void BigInteger::datacopy(BigInteger const& a,SizeT size)
{
for(SizeT i=0;i<size;i++)
TheNumber[Start+i] = a.TheNumber[a.Start+i];
}

// Determines the length upto valid data
SizeT BigInteger::datalen(DATATYPE const* a) const
{
SizeT l = 0;
while(a[l]!=INVALIDDATA) l++;
return l;
}

// Returns number of digits in a BigInteger
SizeT BigInteger::Digits() const
{ return End-Start+1; }

// true if 'this' is zero
bool BigInteger::isZero() const
{ return End==Start && TheNumber[Start]==0; }

// Checks for the validity of the number
bool BigInteger::isValidNumber() const
{
for(SizeT i=Start; i<End ; i++)
if(TheNumber>=BASE) return false;

return true;
}

// Trims Leading Zeros
void BigInteger::TrimZeros()
{
while(TheNumber[Start]==0 && Start<End)
Start++;
}

// Compares this with `with' irrespective of sign
// Returns
// 0 if equal
// 1 if this>with
// -1 if this<with
int BigInteger::UnsignedCompareTo(BigInteger const& with)const
{
if(isZero() && with.isZero()) return 0;
if(!isZero() && with.isZero()) return 1;
if(isZero() && !with.isZero()) return -1;

long temp = Digits() - with.Digits();
// Case 3: First One got more digits
// Case 4: First One got less digits
if(temp!=0) return temp<0?-1:1;

// Now I know Both have same number of digits
// Case 5,6,7:
/*
Compares two array of data considering the
case that both of them have the same number
of digits
*/

temp = 0;
int cmp = 0;
for(SizeT i=0;i<Digits();i++)
{
temp = TheNumber[i+Start] - with.TheNumber[i+with.Start];
if(temp!=0)
{
cmp = temp<0?-1:1;
break;
}
}

return cmp;
}

// Compares this with `with'
// Returns
// 0 if equal
// 1 if this>with
// -1 if this<with
int BigInteger::CompareTo(BigInteger const& with)const
{
int cmp = UnsignedCompareTo(with);

// Case 1: Positive , Negative
if(isNegative==false && with.isNegative==true) return 1;
// Case 2: Negative, Positive
if(isNegative==true && with.isNegative==false) return -1;
// Now, Both are Same Sign
int both_neg = 1;
if(isNegative==true && with.isNegative==true) both_neg = -1;
return cmp*both_neg;
}

// Implentation of addition by paper-pencil method
BigInteger& BigInteger::Add(BigInteger const& Small) const
{
BigInteger const& Big = *this;
BigInteger &Result= *new BigInteger(Big.Digits()+1,0);

long Carry=0,Plus;
long i=Big.Digits() - 1,
j=Small.Digits() -1;

for(; i>=0 ;i--,j--){
Plus = Big.TheNumber[i+Big.Start] + Carry;
if(j>=0) Plus += Small.TheNumber[j+Small.Start] ;

Result.TheNumber[i+1] = Plus%BASE;
Carry = Plus/BASE;
}
i++;

if(Carry) Result.TheNumber[i--] = Carry;

Result.TrimZeros();

return Result;
}

// Implentation of subtraction by paper-pencil method
BigInteger& BigInteger::Subtract(BigInteger const& Small)const
{
BigInteger const& Big = *this;
BigInteger& Result = *new BigInteger(Big.Digits()+1,0);

long Carry=0,Minus;

long i = Big.Digits() - 1,
j= Small.Digits() - 1;

for( ; i>=0 ;i--,j--)
{
Minus = Big.TheNumber[i+Big.Start] - Carry;
if(j>=0) Minus -= Small.TheNumber[j+Small.Start];

if(Minus < 0)
{
Result.TheNumber[i+1] = Minus + BASE;
Carry = 1;
}
else
{
Result.TheNumber[i+1] = Minus;
Carry = 0;
}
}
Result.TrimZeros();
return Result;
}

// Addition operator
BigInteger& operator+(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isNegative && !N2.isNegative)
{
// First is negaive and second is not
BigInteger& Res = *new BigInteger(N1);
Res.isNegative = false;
Res = N2-Res;
return Res;
}
if(!N1.isNegative && N2.isNegative)
{
// Second is negaive and first is not
BigInteger& Res = *new BigInteger(N2);
Res.isNegative = false;
Res = N1-Res;
return Res;
}

BigInteger& ret = *new BigInteger();

if(N1.UnsignedCompareTo(N2)<0)
ret = N2.Add(N1);
else
ret = N1.Add(N2);
if(N1.isNegative==true && N2.isNegative==true)
ret.isNegative = true;
return ret;
}

// Subtruction operator
BigInteger& operator-(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isNegative && !N2.isNegative)
{
BigInteger& res = *new BigInteger(N1);
res.isNegative = false;
res = res+N2;
res.isNegative = true;
return res;
}
if(!N1.isNegative && N2.isNegative)
{
BigInteger& res = *new BigInteger(N2);
res.isNegative = false;
res = res+N1;
return res;
}


BigInteger& ret = *new BigInteger();
int cmp = N1.UnsignedCompareTo(N2);
if(cmp==0)
{
ret = *new BigInteger();
}
if(cmp<0)
{
ret = N2.Subtract(N1);
ret.isNegative = true;
}
else
{
ret = N1.Subtract(N2);
ret.isNegative = false;
}
return ret;
}

// Implentation of multiplication by paper-pencil method
BigInteger& BigInteger::Multiply(BigInteger const& Small) const
{
BigInteger const& Big = *this;
BigInteger& Result = *new BigInteger(Big.Digits()+Small.Digits(),0);

long Carry,Multiply;

SizeT i;
SizeT j;

for(i = 0 ; i< Small.Digits() ; i++)
{
Carry = 0;
for(j = 0 ; j< Big.Digits() ; j++)
{
Multiply = ( (long)Small.TheNumber[Small.End-i] * (long)Big.TheNumber[Big.End-j] )
+ Carry + Result.TheNumber[Result.End-i-j];
Result.TheNumber[Result.End-i-j] = Multiply%BASE;
Carry = Multiply/BASE ;
}
Result.TheNumber[Result.End-i-j] = Carry;
}

Result.TrimZeros();

return Result;
}

// Implentation of multiplication by paper-pencil method
// See: D. E. Knuth 4.3.1
BigInteger& BigInteger::Multiply(DATATYPE const& with) const
{
BigInteger& Result = *new BigInteger(Digits()+1,0);

long Carry,Multiply;

SizeT i;

Carry = 0;
for(i = 0 ; i< Digits() ; i++)
{
Multiply = Carry + (long)TheNumber[End-i] * (long)with;
Carry = Multiply / BASE;
Result.TheNumber[Result.End-i] = Multiply % BASE;
}
Result.TheNumber[Result.End-i] = Carry;
Result.TrimZeros();

return Result;
}

// Multiplication operator
BigInteger& operator*(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isZero() || N2.isZero()) return *new BigInteger();
BigInteger& ret = *new BigInteger();
if(N1.UnsignedCompareTo(N2)<0)
ret = N2.Multiply(N1);
else
ret = N1.Multiply(N2);
if(N1.isNegative!=N2.isNegative)
ret. isNegative = true;
return ret;
}

// Multiplication operator
BigInteger& operator*(BigInteger const& N1, DATATYPE const& N2)
{
if(N1.isZero() || N2==0) return *new BigInteger();
BigInteger& ret = N1.Multiply(N2);
// if(N1.isNegative!=(N2<0)) ret. isNegative = true;
return ret;
}

// Multiplication operator
BigInteger& operator*(DATATYPE const& N1, BigInteger const& N2)
{
if(N2.isZero() || N1==0) return *new BigInteger();
BigInteger& ret = N2.Multiply(N1);
// if(N2.isNegative!=(N1<0)) ret. isNegative = true;
return ret;
}

// Implentation of division by paper-pencil method
// Here `this' is divided by 'V'
BigInteger& BigInteger::DivideAndRemainder(DATATYPE const& V,DATATYPE& _R,bool skipRemainder=false) const
{
BigInteger& W = *new BigInteger(Digits(),0,false);
DATATYPE R = 0;
SizeT j;
for(j=0;j<=End;j++)
{
W.TheNumber[j] = (R*BASE+TheNumber[Start+j])/V;
R = (R*BASE+TheNumber[Start+j])%V;
}

W.TrimZeros();
if(skipRemainder==false)
_R = R;

return W;
}

// Implentation of division by paper-pencil method
// Does not perform the validity and sign check
// It is assumed that this > `_V'
// See: D.E.Knuth 4.3.1
BigInteger& BigInteger::DivideAndRemainder(BigInteger const& _V,BigInteger& R,bool skipRemainder=false) const
{
SizeT m = this->Digits()-_V.Digits();
SizeT n = _V.Digits();
BigInteger& Q = *new BigInteger(m+1,0,false);

DATATYPE d, qhat, rhat;
long temp,x,y;
SizeT i;
int j;

d = (BASE-1)/_V.TheNumber[_V.Start];

BigInteger& U = this->Multiply(d);
BigInteger& V = _V.Multiply(d);

for(j = m; j>=0; j--)
{
temp = (long)U.TheNumber[U.End-j-n]*(long)BASE + (long)U.TheNumber[U.End-j-n+1];
x = temp / (long)V.TheNumber[V.Start];
y = temp % (long)V.TheNumber[V.Start];
if(x>(long)BASE) x /= BASE;
if(y>(long)BASE) y %= BASE;
qhat = (DATATYPE) x;
rhat = (DATATYPE) y;

bool badRhat = false;
do
{
x = (long)qhat * (long)V.TheNumber[V.Start+1];
y = (long)BASE*(long)rhat + (long)U.TheNumber[U.End-j-n+1];

if(qhat==BASE || x > y)
{
qhat --;
rhat += V.TheNumber[V.Start];
if(rhat<BASE) badRhat = true;
else badRhat = false;
}
else break;
}while(badRhat);

// `x' Will act as Carry in the next loop
x = 0;
temp = 0;
for(i=0;i<=n;i++)
{
if(V.End>=i) temp = (long)qhat*(long)V.TheNumber[V.End-i] + temp;
y = (long)U.TheNumber[U.End-j-i] - temp%BASE - x;
temp /= BASE;
if(y < 0)
{
U.TheNumber[U.End-j-i] = (DATATYPE)(y+BASE);
x = 1;
}
else
{
U.TheNumber[U.End-j-i] = (DATATYPE)y;
x = 0;
}
}
// if(x) U.TheNumber[U.Start+j+i] --;

Q.TheNumber[Q.End-j] = qhat;

if(x)
{
Q.TheNumber[Q.End-j] --;
// `x' Will act as Carry in the next loop
x = 0;
for(i=0;i<=n;i++)
{
y = (long)U.TheNumber[U.End-j-i] + x;
if(V.End>=i) y += (long)V.TheNumber[V.End-i];
U.TheNumber[U.End-j-i] = (DATATYPE)(y % BASE);
x = y / BASE;
}
U.TheNumber[U.End-j-i] = (DATATYPE)x;
}
}

U.TrimZeros();
DATATYPE _t;
if(skipRemainder==false)
R = U.DivideAndRemainder(d,_t,true);
Q.TrimZeros();

return Q;
}

// Front end for Divide and Remainder
// Performs the validity and sign check
BigInteger& DivideAndRemainder(BigInteger const& U, BigInteger const& V,BigInteger& R,bool skipRemainder=false)
{
//if(V.isZero())
// throw logic_error (DumpString ("DivideAndRemainder (BigInteger/BigInteger)",BigMathDIVIDEBYZERO));

if(U.isZero())
{
R = *new BigInteger();
return *new BigInteger();
}

int cmp = U.UnsignedCompareTo(V);
if(cmp==0)
{
R = *new BigInteger();
BigInteger& W = *new BigInteger(1l);
if(U.isNegative!=V.isNegative) W.isNegative = true;
return W;
}
else if(cmp<0)
{
R = *new BigInteger(U);
if(U.isNegative!=V.isNegative) R.isNegative = true;
return *new BigInteger();
}
BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder);
if(U.isNegative!=V.isNegative) ret.isNegative = true;
return ret;
}

// Front end for Divide and Remainder
// Performs the validity and sign check
BigInteger& DivideAndRemainder(BigInteger const& U, DATATYPE const& V,DATATYPE& R,bool skipRemainder=false)
{
// if(V==0)
// throw logic_error ( DumpString ("DivideAndRemainder (BigInteger/DATATYPE)",BigMathDIVIDEBYZERO) );

if(U.isZero())
{
R = 0;
return *new BigInteger();
}

int cmp = 1;
if(U.Digits()==1)
{
if(U.TheNumber[U.Start]<V) cmp = -1;
else if(U.TheNumber[U.Start]>V) cmp = 1;
else cmp = 0;
}
if(cmp==0)
{
R = 0;
return *new BigInteger(1l);
}
else if(cmp<0)
{
R = U.TheNumber[U.Start];
return *new BigInteger();
}
BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder);
// if(U.isNegative!=(V<0)) ret.isNegative = true;
return ret;
}

// Division operator
BigInteger& operator/(BigInteger const& N1, BigInteger const& N2)
{
BigInteger& R = *new BigInteger();
return DivideAndRemainder(N1,N2,R,true);
}

// Division operator
BigInteger& operator/(BigInteger const& U, DATATYPE const& V)
{
DATATYPE R;
return DivideAndRemainder(U,V,R,true);
}

// Division operator
BigInteger& operator/(DATATYPE const& U, BigInteger const& V)
{
if(V.Digits()==1 && U>V.TheNumber[V.Start])
{
return *new BigInteger(U/V.TheNumber[V.Start]);
}
return *new BigInteger();
}

// Modulus operator
BigInteger& operator%(BigInteger const& N1,BigInteger const& N2)
{
BigInteger& R = *new BigInteger();
DivideAndRemainder(N1,N2,R);
return R;
}

// Modulus operator
BigInteger& operator%(BigInteger const& U, DATATYPE const& V)
{
DATATYPE R;
DivideAndRemainder(U,V,R);
return *new BigInteger(R);
}

// Modulus operator
BigInteger& operator%(DATATYPE const& U, BigInteger const& V)
{
if(V.Digits()==1 && U>V.TheNumber[V.Start])
{
return *new BigInteger(U%V.TheNumber[V.Start]);
}
return *new BigInteger();
}

// Assignment Operator
BigInteger& BigInteger::operator=(BigInteger const&arg)
{
Start = 0;
End = arg.Digits() - 1;
delete [] TheNumber;
TheNumber = new DATATYPE [arg.Digits()];

datacopy(arg,arg.Digits());
isNegative = arg.isNegative;
return *this;
}

// Inserter
ostream& operator<<(ostream& stream, BigInteger const& out)
{
if(out.isNegative==true && out.isZero()==false) stream << '-';
stream << out.TheNumber[out.Start];
for(SizeT i=out.Start+1;i<=out.End;i++)
{
stream.width(4);
stream.fill('0');
stream << out.TheNumber;
}

return stream;
}

// Extracter
istream& operator>>(istream& stream, BigInteger& in)
{
SizeT SIZE = 500;
char *data = new char[SIZE];
// if(data==0) Dump("Extractor operator",BigMathMEM);
SizeT i = 0;
int input;
bool isNegative = false;

if(stream.eof())
return stream;
stream >> ws;

if(stream.eof())
return stream;
input = stream.get();

if(input=='-')
isNegative = true;
else if(input=='+')
isNegative = false;
else
stream.putback(input);

while(true)
{
input = stream.get();
if(stream.eof())
break;

if(isdigit(input))
data[i++] = input;
else
{
stream.putback(input);
break;
}
if(i>=SIZE)
{
SIZE += SIZE;
char *p = new char [SIZE];
// if(p==0) Dump("Extractor operator",BigMathMEM);
strcpy(p,data);
delete [] data;
data = p;
}
}
data = 0;
in = *new BigInteger(data);
if(in.isZero()==false)
in.isNegative = isNegative;
return stream;
}

// Inserts the version information into the output stream
ostream& BigIntegerVersion(ostream& out)
{
out << BigIntPROGRAMNAME << " (Version "<< BigIntMajorVersion
<< "." << BigIntMinorVersion << "." << BigIntRevision << ")";
return out;
}

// Inserts the author information into the output stream
ostream& BigIntegerAuthor(ostream& out)
{
out << "Author: " << AuthorName << endl
<< "mailto: ";
int i = 0;
while(AuthorEmail!=NULL)
{
if(i!=0) out << ", ";
out << AuthorEmail[i++];
}
return out;
}

// Inserts the last update date into the output stream
ostream& BigIntegerLastUpdate(ostream& out)
{
out << "Last Updated: " << LastUpdated;
return out;
}

// Inserts the about information into the output stream
ostream& BigIntegerAbout(ostream& out)
{
out << BigIntegerVersion << endl
<< BigIntegerLastUpdate << endl
<< BigIntegerAuthor << endl;
return out;
}

// Returns a string containing version information
string& BigIntegerVersionString()
{
char out[100];
ostrstream str(out,sizeof(out));
str << BigIntegerVersion;
return *new string(out);
}

// Converts `this' to a string representation
string& BigInteger::toString()const
{
const int DIGITS = Digits()*4;
char *R = new char[DIGITS+2];
ostrstream ostr(R,DIGITS);
ostr << *this;
return *new string(R);
}

// Converts `this' to equivalent int value
int BigInteger::toInt()
{
return (int)toLong();
}

// Converts `this' to equivalent 32 bit long value
long BigInteger::toLong()
{
long r = TheNumber[End];
if(Digits()>1) r += BASE * TheNumber[End-1] ;
if(Digits()>2) r += BASE*BASE*(TheNumber[End-2]%100);
return r;
}

// Postfix Increment , that is *this++
BigInteger& BigInteger::operator++()
{
BigInteger& ONE = *new BigInteger(1l);
*this = *this+ONE;
return *this;
}

// Prefix Increment , that is ++*this
BigInteger& BigInteger::operator++(int notused)
{
BigInteger one(1l);
BigInteger& Ret = *new BigInteger(*this);
*this = *this+one;
return Ret;
}

// Postfix Decrement , that is *this--
BigInteger& BigInteger::operator--()
{
BigInteger one(1l);
*this = *this-one;
return *this;
}

// Pretfix Increment , that is --*this
BigInteger& BigInteger::operator--(int notused)
{
BigInteger one(1l);
BigInteger& Ret = *new BigInteger(*this);
*this = *this-one;
return Ret;
}

// Negation, returns -*this
BigInteger& BigInteger::operator-()
{
this->isNegative = this->isNegative==true?false:true;
return *this;
}

DATATYPE& BigInteger::operator[](unsigned int pos) const
{
//if(pos<Start || pos>End)
//throw domain_error ( DumpString("operator[]", BigMathDomain) );

return TheNumber[pos];
}

// Left Shift
// To be checked
BigInteger& BigInteger::operator<<(SizeT b)
{
SizeT i = (SizeT)(b / LOG10BASE);
b %= LOG10BASE;
while(b--) TheNumber[Digits()-1] *= 10;

if(i>0)
{
DATATYPE *temp = new DATATYPE[Digits()+i];
for(b=0;b<Digits();b++)
temp = TheNumber;
for(b=0;b<i; b++)
temp[Digits()+b] = 0;
delete [] TheNumber;
TheNumber = temp;
End += i-1;
}
return *this;
}

// Right Shift
BigInteger& BigInteger::operator>>(SizeT b)
{
SizeT i = (SizeT)(b / LOG10BASE);
b %= LOG10BASE;
End -= i;
while(b--)
{
DATATYPE f = 0,l = 0;
for(i=Start;i<=End;i++)
{
l = TheNumber%10;
TheNumber = f*BASE + TheNumber/10;
f = l;
}
if(TheNumber[Start]==0)
Start--;
}
return *this;
}

// Makes `this' BigInteger value to absolute
void BigInteger::abs()
{ isNegative = false; }

// Returns new BigInteger value which is absolute
// copy of `arg'
BigInteger& abs(BigInteger& arg)
{
BigInteger& ret = *new BigInteger(arg);
ret.isNegative = false;
return ret;
}

// Power BigInteger to the power Long
BigInteger& BigInteger::Power(long y) const
{
long P;
BigInteger& pow = *new BigInteger(1l);
BigInteger& z = *new BigInteger();
BigInteger& ZERO = *new BigInteger();
BigInteger& ONE = *new BigInteger(1l);
P = y;

if(y==0) return pow;
if(isZero()) return ZERO;
if(UnsignedCompareTo(ONE)==0) return ONE;

z = *this;
while(P>0)
{
while(P%2==0)
{
P /= 2;
z = z*z;
}
P--;
pow = pow*z;
}
return pow;
}

void Dump(char const* s,enum BigMathERROR e)
{
cerr << BigIntegerVersion << endl;
cerr << "Exception: " << BigIntErrDes[e-1] << endl;
cerr << "In function: " << s << endl;
cerr << "Error Code: " << e << endl;
exit(e);
}

string& DumpString (char const* s,enum BigMathERROR e)
{
char *R = new char[256];
ostrstream ostr(R,255);
ostr << BigIntegerVersion << endl;
ostr << "Exception: " << BigIntErrDes[e-1] << endl;
ostr << "In function: " << s << endl;
ostr << "Error Code: " << e << endl;
return *new string(R);
}

BigInteger& BigInteger::OldSquareRoot() const
{
BigInteger const& n = *this;
BigInteger& _2 = *new BigInteger(2l);
BigInteger& zero = *new BigInteger();
if(n.isZero())
return zero;

//if(n.isNegative)
// throw domain_error ( DumpString ("SquareRoot",BigMathDomain) );

long Dig;
if(n.Digits()%2==0)
Dig = n.Digits()/2 - 1;
else
Dig = n.Digits()/2 ;

BigInteger& sq = *new BigInteger(1l);
if(Dig==-1)
return sq;

BigInteger sqr,toIncrease,temp;
sq = sq << Dig;
toIncrease = sq;

while(true)
{
sqr = sq*sq;
if(sqr.CompareTo(n) == 0) break;
if(toIncrease.CompareTo(zero)==0) break;
if(sqr.CompareTo(n) > 0)
{
toIncrease = toIncrease/_2;
sq = temp;
}

temp = sq;
sq = sq + toIncrease;
}
return sq;
}

BigInteger& BigInteger::SquareRoot() const
{
if(isZero())
return *new BigInteger();

//if(isNegative)
//throw domain_error ( DumpString ("SquareRoot",BigMathDomain) );

BigInteger& result = *new BigInteger(Digits(),0,false);
SizeT i = 1;

result[result.Start] = sqrt((double)TheNumber[Start]);
BigInteger& remainder = *new BigInteger(
TheNumber[Start] - result[result.Start] * result[result.Start] );
BigInteger& temp = *new BigInteger(result);
temp.Multiply(2);
double rlim, llim;

while(true)
{
// remainder = remainderBASE * TheNumber[i];
// rlim = remainder
}

delete &temp;
delete &remainder;

return result;
}

bool operator==(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)==0; }

bool operator!=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)!=0; }

bool operator>=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)>=0; }

bool operator<=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)<=0; }

bool operator>(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)>0; }

bool operator<(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)<0; }

typedef BigInteger bint;
}



/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/



//#include "BigInteger.h"
// put BigInteger.h in the same folder
// if you want to submit to UVa judge, copy all the content of BigInteger.h
// and paste it here...

using namespace BigMath; // compulsory
BigInteger Fib(int n) {
int N = n;
BigInteger h((long)1),i((long)1),j,k,t;
while (n > 0) {
if (n%2 == 1) { // if n is odd
t = j*h;
j = i*h + j*k + t;
i = i*k + t;
}
t = h*h;
h = 2*k*h + t;
k = k*k + t;
n = (int) n/2;
}
return j;
}


int main()
{
int n;
while(cin >> n)
{
cout << "The Fibonacci number for " << n << " is " << Fib(n) << endl;
}
return 0;
}
[/cpp]

[trashmai]

I've tried again and again for this problem, and always got WAs.

And I've modified my code several times, check the answer with friends, did something like that all night, but i just can't figure it out why.

I've also tried some different OS, different compiler..just don't know..don't understand..

Or does this problem have some special requirement?

[c]

#include <stdio.h>

long num1[400];
long num2[400];

struct {
long v[400];
int l;
} fibo[5002];

int l=1;
int i=0,j=1,k,maxn;

void plus(long *num1,long *num2,int *l){
int i;
for (i=0;i<*l;i++){
num1=num1+num2;
if (num1>=10000) {
if (i == (*l)-1)
(*l)++;
num1 %= 10000;
num1[i+1]+=1;
}
}
if (num1[*l+1]!=0) (*l)++;
}


void getfib(int n){
for (i=(maxn/2)+(maxn%2)-1;i<n/2+n%2-1;i++){
plus(num1,num2,&l);
for (k=0;k<l;k++){
fibo[j].v[k]=num1[k];
fibo[j].l=l;
}
j++;
plus(num2,num1,&l);
for (k=0;k<l;k++){
fibo[j].v[k]=num2[k];
fibo[j].l=l;
}
j++;
}
maxn=n;
}

int main(void){

int n;
num1[0]=0;
num2[0]=1;

while (scanf("%d",&n)==1){

if (n>maxn) getfib(n);

printf("The Fibonacci number for %d is ",n);
if (n==0) {printf("0\n");}
else if (n==1) {printf("1\n");}
else{
for (i=fibo[n-1].l-1;i>=0;i--){
if (i!=fibo[n-1].l-1){
if (fibo[n-1].v/1000 == 0){
printf("0");
if (fibo[n-1].v/100 == 0){
printf("0");
if (fibo[n-1].v/10 == 0){
printf("0");
if (fibo[n-1].v == 0){
printf("0");
}
}
}
}
}
if ((i!=fibo[n-1].l-1)||(fibo[n-1].v[fibo[n-1].l-1]!=0)||(i==0)) printf("%ld",fibo[n-1].v);
}
printf("\n");
}
}
return 0;
}

[/c]

[mattapayne]

I can't seem to get past this:

02919915_24.c: In function `class string addStrings(basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >, basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >)':
02919915_24.c:97: implicit declaration of function `int itoa(...)'


Is this a compile error specific to gcc? I don't get this error compiling using VC++. Is there any way around it?

Thanks,
Matt

[UFP2161]

itoa is not part of the ANSI standard.. you'll have to write your own.. or use sscanf instead..