495 - Fibonacci Freeze

[Ghost77 dimen]

Try BigInt.

An array to simulate an integer.

[Riyad]

i tried the big int but i dont know wht the prob is . i used the class big int to simulate this. pliz help;here is my code
#include <iostream.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>




int BigIntMajorVersion = 6;
int BigIntMinorVersion = 7;
int BigIntRevision = 25;

typedef unsigned int SizeT;
typedef unsigned int DATATYPE;

const DATATYPE BASE = 10000;
const DATATYPE INVALIDDATA = 65535U;
const SizeT LOG10BASE = 4;


class BigInteger
{
private:
DATATYPE *TheNumber;
SizeT Start;
SizeT End;
bool isNegative;

BigInteger(SizeT,DATATYPE,bool);

void datacopy(BigInteger const&,SizeT);

SizeT datalen(DATATYPE const*) const;
void deallocateBigInteger();
void TrimZeros();
void Set(DATATYPE);

public:
BigInteger();
BigInteger(long);
BigInteger(char const*);
BigInteger(BigInteger const&);

~BigInteger();

int UnsignedCompareTo(BigInteger const&)const;
int CompareTo(BigInteger const&)const;

SizeT Digits() const;
bool isValidNumber() const;
bool isZero()const;

BigInteger& Add(BigInteger const&) const;
BigInteger& Subtract(BigInteger const&) const;
BigInteger& Multiply(BigInteger const&) const;
BigInteger& Multiply(DATATYPE const&) const;
BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const;
BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) const;


friend BigInteger& operator+(BigInteger const&, BigInteger const&);
friend BigInteger& operator-(BigInteger const&, BigInteger const&);
friend BigInteger& operator*(BigInteger const&, BigInteger const&);
friend BigInteger& operator*(BigInteger const&, DATATYPE const&);
friend BigInteger& operator*(DATATYPE const&, BigInteger const&);
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&);
friend BigInteger& operator%(BigInteger const&, BigInteger const&);
friend BigInteger& operator%(BigInteger const&, DATATYPE const&);
friend BigInteger& operator%(DATATYPE const&, BigInteger const&);

BigInteger& operator=(BigInteger const&);

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


BigInteger& operator++();
BigInteger& operator++(int);

BigInteger& operator--();
BigInteger& operator--(int);

BigInteger& operator-();


BigInteger& operator<<(SizeT);
BigInteger& operator>>(SizeT);
void abs();
friend BigInteger& abs(BigInteger&);

int toInt();
long toLong();

BigInteger& Power(long )const;
BigInteger& SquareRoot() const;
};

here is the main
BigInteger zero("0"), one("1");
BigInteger two(2);
BigInteger fib[5010];



int main(){


register int i, num;

fib[0] = zero;
fib[1] = one;

freopen("input.in","rt",stdin);

for(i = 2; i <= 5005; i++)
{
fib = fib[i-1] + fib[i-2];
}

while(scanf("%d", &num) != EOF)
{
cout<<fib[num]<<endl;
}
return 0;



return 0;

}


sorry for being stupid and to send such a big code . looking forward for u r help.
Riyad

[UFP2161]

The output is supposed to look like:

The Fibonacci number for 5 is 5

? =P

[Riyad]

sorry bossssssssssssss so stupid of me . i should have checked the output format. this is really careless stuff.

so nice of u big bro s to help we new people out here .
thanx

Riyad

[Mage]

In solving program number 495, it's better to use looping(do, while, for). I mean that you just input the number and in the statement "for" you make the condition.

[Admus]

var
a,w:longint;
fib:array[0..5000]of string;

Function dod(s,wyn:string):string;
var
w,a,pom1,pom2,d1,d2,reszta:longint;
begin
while length(s)<length(wyn) do
s:='0'+s;
while length(s)>length(wyn) do
wyn:='0'+wyn;
d1:=length(s);
d2:=length(wyn);
reszta:=0;
for d1:=d1 downto 1 do
begin
pom1:=ord(wyn[d1])-48;
pom2:=ord(s[d1])-48;
if pom1+pom2+reszta<10 then
begin
w:=pom1+pom2+reszta;
reszta:=0
end
else
begin
w:=pom1+pom2+reszta-10;
reszta:=1;
end;
wyn[d1]:=chr(w+48);
if d1=1 then
if reszta=1 then
wyn:='1'+wyn;
end;
dod:=wyn;
end;
begin
fib[0]:='0';
fib[1]:='1';
fib[2]:='1';
for a:=3 to 50 do
begin
fib[a]:=fib[a-1];
fib[a]:=dod(fib[a-1],fib[a-2]);
end;
while not eof do
begin
readln(w);
writeln('The Fibonacci number for',' ',w,' ','is',' ',fib[w]);
end;
end.

[playerX]

please highlight your code for a bit more clarity, thanks...

[Eduard]

can someone help me i got time limit exceeded in problem 495(fibonachi).
my program is rigth and it works 1second when n=5000 i thing i'm doing
something wrong with input.is this problem input while not eof or ...?

[Larry]

Cache it so you won't keep calculating..

[Admus]

Sorry, I just know what is wrong with it.

[Eduard]

and what i can du for geting AC this problem.
I wrote it in Pascal.

[Dominik Michniewski]

Think about input like

5000 (hundred time)
...
4999 (hundred time)
...
and so on ...

Best regards
DM

[Joseph Kurniawan]

Make a function to calculate and store the fibonacci number 0-5000 before running the main function. With this technique, the main function will only have to output the stored fibo number!!
Good luck!!

[amiboshi]

program high_add;

type num=array [0..5000] of integer;
var a,b,c,d:ansistring;
n1,n2,n3:num; ans:array [0..5000] of ansistring;
i:integer;
procedure extract(var k:num;var s:ansistring);
var i,e:integer;
begin
while length(s) mod 4<>0 do
s:='0'+s;
for i:=1 to length(s) div 4 do
val(copy(s,(i-1)*4+1,4),k,e);
end;

procedure add(var k1,k2,sum:num);
var total,up,remain,i:integer;

begin
remain:=0;
up:=0;
for i:=length(a) div 4 downto 1 do
begin
total:=k1+k2;
up:=total div 10000;
remain:=total mod 10000;
sum:=remain+sum;
if up <>0 then sum[i-1]:=up;
end;
end;

procedure convert(sum:num;var s:ansistring);
var i:integer;temp:ansistring;
begin
temp:='';
if sum[0]<>0 then
str(sum[0],temp);
s:=temp;

for i:=1 to length(a) div 4 do
begin
str(sum,temp);
if s<>'' then
while length(temp)<4 do
temp:='0'+temp;
s:=s+temp
end;
end;


begin
c:='0';
a:='1';
b:='1';
d:='1';
fillchar(n1,sizeof(n1),0);
fillchar(n2,sizeof(n2),0);
fillchar(n3,sizeof(n3),0);
fillchar(ans,sizeof(ans),0);
for i:=1 to 5000 do
if length(ans)=0 then
begin
b:=c;
a:=d;
d:=c;
fillchar(n1,sizeof(n1),0);
fillchar(n2,sizeof(n2),0);
fillchar(n3,sizeof(n3),0);
while length(a)<>length(b) do
if length(a)>length(b) then b:='0'+b
else if length(b)>length(a) then a:='0'+a;
extract(n1,a);
extract(n2,b);
add(n1,n2,n3);
convert(n3,c);
ans:=c;
end else begin c:=ans;d:=ans[i-1];end;
ans[0]:='0';
(* Calculate it first *)

while not eof do begin
readln(i);
writeln('The Fibonacci number for ',i,' is ',ans);

end;

end.

[rlatif119]

I got TLE....i think my addition is correct. i check for many outputs including 5000.....and i found it correct....but l got TLE. I precalculate the numbers and store it and then just ouput according to the input. Can anybody find out the problem please. Better copy this code and run and figure out the problem.
HERE IS MY CODE....
[c]
#include<stdio.h>
#include<string.h>



struct list{
char num[1500];
};
struct list fib[5000];
void calculate_and_store(void);


main()
{
int n,i;

calculate_and_store();
while(1)
{
scanf("%d",&n);
if(feof(stdin))
break;
if(n==0)
printf("The Fibonacci number for %d is 0\n",n);
else
printf("The Fibonacci number for %d is %s\n",n,fib[n-1].num);
}
}
void calculate_and_store(void)
{
char a[1500],b[1500],temp[1500],c[1500];
int n,i,len1,len2,len3,j,k,l;
int sum;

strcpy(fib[0].num,"1");

for(n=2;n<=5000;++n)
{
strcpy(a,"0");
strcpy(b,"1");
strcpy(c,"");

for(i=2;i<=n;++i)
{

strcpy(temp,"");
len1=strlen(a);
len2=strlen(b);
l=0;sum=0;
for(j=len1-1,k=len2-1; j>=0 && k>=0 ;--j,--k)
{
sum= sum + (a[j]-48 ) + (b[k]-48 );
if(sum>9)
{
temp[l++]=(sum%10)+48;
sum = sum/10;
}
else
{
temp[l++]=sum+48;
sum=0;
}
}
if(j<0 && k>=0)
{
while(k>=0)
{
sum = sum + (b[k]-48 );
--k;
if(sum>9)
{
temp[l++]=(sum%10)+48;
sum = sum/10;
}
else
{
temp[l++]=sum+48;
sum=0;
}
}
}

if(j>=0 && k<0)
{
while(j>=0)
{
sum = sum + (a[j]-48 );
--j;
if(sum>9)
{
temp[l++]=(sum%10)+48;
sum = sum/10;
}
else
{
temp[l++]=sum+48;
sum=0;
}
}
}
if(sum>0)
temp[l++]=sum+48;
temp[l]='\0';
len3 = strlen(temp);

for(j=0,k=len3-1;k>=0;--k)
c[j++]=temp[k];
c[j]='\0';
strcpy(a,b);
strcpy(b,c);
}

strcpy(fib[n-1].num,c);

}
}[/c]