## 495 - Fibonacci Freeze

Moderator: Board moderators

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### Still got WA

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:
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 (val<0 || val>5000) return 1;
the same result occurs.

Thanks,
Mark

MAXX^FACTOR
New poster
Posts: 7
Joined: Mon Sep 16, 2002 7:29 am
Location: EARTH.ASIA.TAIWAN.TAIPEI
Contact:

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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### I really wonder..

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)
New poster
Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh
Contact:

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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

### 495:WHY compile error?

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]);

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
New poster
Posts: 2
Joined: Thu Mar 13, 2003 9:11 pm
Contact:

### Re: 495:WHY compile error?

[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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

### thanx man!

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
Wisdom is know what to do next; virtue is doing it.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### 495 - Fibonacci Freeze - why it is wrong answer ?

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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I try to pre-calc. the first 5000th fibs. But I still get TLE......

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

[pascal]* Deleted *[/pascal]
Last edited by Observer on Sun May 18, 2003 1:37 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### 495 Why RunTimeError?

[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
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
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.