495 - Fibonacci Freeze

[Adrian Kuegel]

Thats precision error, and you can't use long double for this question, as far as I know. It's a BigInteger problem.

[Betovsky]

whats the difference between integer and double if i only sums ???

Explain to me ... it must be something out of my knowledge...

Thx.

[Adrian Kuegel]

I think it has something to do with the floating point format. There is one sign bit, some exponent bit (I don't know the exact number) and the remaining bits are used to form a number 1.xxxxxxxxxx in binary representation. If you have a number which would use more bits, than it is rounded. You get Infinity if the bits of the exponent are not enough.

[Betovsky]

yes ... of course ...

hehe i forgot that in doubles they are represented in exponecial of 10

Thx

[Stefan Pochmann]

They are not, doubles use base 2.

[Betovsky]

base 2, base 10 sme problem

[zakaria]

Can anyone tell me why this code of mine is W.A?

#include<iostream.h>
#include<string.h>
int main()
{

char *fibo[5001]={0};
fibo[0]="0";
fibo[1]="1";
int l1=strlen(fibo[0]);
int l2=strlen(fibo[1]);
int l;
for(long i=2;i<=5000;i++)
{
char str[10000];
if(l1>=l2)l=l1;
else l=l2;
int ca=0;
long j,k,m,p;
for(j=l1-1,k=l2-1,m=0,p=0;p<l;j--,k--,m++,p++)
{
int s1;
if(j<0)fibo[i-2][j]='0';
s1=fibo[i-2][j]-48;
int s2;
if(k<0)fibo[i-1][k]='0';
s2=fibo[i-1][k]-48;
int ans=0;
ans+=s1+s2+ca;
if(ans>9)
{
str[m]=(ans-10)+48;
ca=1;
}
else
{
str[m]=ans+48;
ca=0;
}

}
if(ca>0){str[m]=ca+48; m++;}
str[m]='\0';
fibo=new char[m+1];
long y=0;
for(long x=m-1;x>=0;x--,y++)fibo[y]=str[x];
fibo[y]='\0';
l1=strlen(fibo[i-1]);
l2=strlen(fibo);
}


int n;
while(cin>>n&&n>0)
{
cout<<"The Fibonacci number for "<<n<<" is "<<fibo[n]<<"\n";
}
return 0;
}

[zakaria]

Can anyone help me with 495?
Why my code get W.A.??

#include<iostream.h>
#include<string.h>
int main()
{

char *fibo[5001]={0};
fibo[0]="0";
fibo[1]="1";
int l1=strlen(fibo[0]);
int l2=strlen(fibo[1]);
int l;
for(long i=2;i<=5000;i++)
{
char str[10000];
if(l1>=l2)l=l1;
else l=l2;
int ca=0;
long j,k,m,p;
for(j=l1-1,k=l2-1,m=0,p=0;p<l;j--,k--,m++,p++)
{
int s1;
if(j<0)fibo[i-2][j]='0';
s1=fibo[i-2][j]-48;
int s2;
if(k<0)fibo[i-1][k]='0';
s2=fibo[i-1][k]-48;
int ans=0;
ans+=s1+s2+ca;
if(ans>9)
{
str[m]=(ans-10)+48;
ca=1;
}
else
{
str[m]=ans+48;
ca=0;
}

}
if(ca>0){str[m]=ca+48; m++;}
str[m]='\0';
fibo=new char[m+1];
long y=0;
for(long x=m-1;x>=0;x--,y++)fibo[y]=str[x];
fibo[y]='\0';
l1=strlen(fibo[i-1]);
l2=strlen(fibo);
}


int n;
while(cin>>n&&n>0)
{
cout<<"The Fibonacci number for "<<n<<" is "<<fibo[n]<<"\n";
}
return 0;
}

[Ivan Golubev]

while(cin>>n&&n>0)

Why do you think that zero means end of input file?

[Picard]

you stop at '0', but it's a valid input

[zakaria]

At last it has accepted.
Thanks to all for reply.

[hsihsiwu]

while(cin>>n&&n>0)

have to change into while(cin>>n&&n>=0)

[zakaria]

Thanks for reply.
It had accepted.

[ec3_limz]

Got WA, but dunno whats wrong.

My Algo: I used base 1000000000 integer arrays to store the Factorial numbers.

Please help.

[cpp]/* @JUDGE_ID: 18472KP 495 C++ */

#include <stdio.h>

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

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

fact[0][89] = 0;
fact[1][89] = 1;
for (i = 2; i <= 5000; i++)
for (j = 89; 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 < 90; i++) {
if (start == 0 && fact[index] > 0)
start = 1;
if (start == 1) {
printf("%d", fact[index]);
start++;
}
else if (start > 1)
printf("%08d", fact[index][i]);
}
printf("\n");
}

return 0;
}[/cpp]

[Ivor]

Shouldn't you have

Code: Select all

printf("%09d", fact[index][i]);

Forgot to mention: 90 ints is not enough. 5000th fibonacci number has over 1000 digits, so 90 * 9 = 810...

Ivor