## 495 - Fibonacci Freeze

Moderator: Board moderators

New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

### Re: 495 - Fibonacci Freeze

can someone tell me why i was getting TLE when my array was for the first 5000 and when i changed it to 5050 it worked in 0.6 ?!!?!?!!?!
kia.masster
New poster
Posts: 6
Joined: Thu Dec 22, 2011 8:47 am

### Re: 495 - Fibonacci Freeze

I got TL for this problem. My algorithm that find n'th fibonacci number is not fast. Can someone help me?

Code: Select all

``````int main(){
int n;
while (cin >> n)
{
bignum a, b;
a = bignum();   // This means a = 0
b = bignum();
b.digits = 1;
b.a[0] = '1';    // This means b = 1
if (n == 0)
cout << "The Fibonacci number for " << n << " is " << a << endl;
else
{
for (int i = 2; i <= n; i++)
{
bignum c = b;
b  = b + a;
a = c;
}
cout << "The Fibonacci number for " << n << " is " << b << endl;
}
}
}``````
I have created an operator to cout bignum and an operator to add two bignum before...
Thank you!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Precompute.
Check input and AC output for thousands of problems on uDebug!
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### Re: 495 - Fibonacci Freeze

Hello
Why am I getting Runtime error?

Code: Select all

``````import java.io.*;
import java.util.Scanner;

class Main {

public static void main(String[] args) {

BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

long[] fibonacci = new long[5000];
fibonacci[1] = 1;
for (int i = 2; i < fibonacci.length; i++) {
fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1];
}
try {
while (scanner.hasNextInt()) {
int i = scanner.nextInt();
writer.write("The Fibonacci number for " + i + " is " + fibonacci[i] + "\n");
}
writer.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
}
``````
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Try input 5000
Check input and AC output for thousands of problems on uDebug!
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### Re: 495 - Fibonacci Freeze

I've changed my code but still get RE

Code: Select all

``````import java.io.*;
import java.util.Scanner;

class Main {

public static void main(String[] args) {

String text = "5\n" +
"7\n" +
"11";

BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

long[] fibonacci = new long[5000];
fibonacci[1] = 1;
for (int i = 2; i <= fibonacci.length; i++) {
fibonacci[i] = fibonacci[i - 2] + fibonacci[i - 1];
}
try {
while (scanner.hasNextInt()) {
int i = scanner.nextInt();
writer.write("The Fibonacci number for " + i + " is " + fibonacci[i] + "\n");
}
writer.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
}
``````
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Try input 5000
Check input and AC output for thousands of problems on uDebug!
darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 495 - Fibonacci Freeze

Why is this a WA?

Code: Select all

``Code Accpeted``
Last edited by darksk4 on Wed Aug 01, 2012 10:34 am, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Don't print blank lines in the output.
Check input and AC output for thousands of problems on uDebug!
darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 495 - Fibonacci Freeze

What do you mean blank lines? the newline? hmmm I already tried it but still WA...
or maybe if the input of the user is greater than 5000 its gives nothing?
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Sample input:

Code: Select all

``````5
7
11``````
Correct output:

Code: Select all

``````The Fibonacci number for 5 is 5
The Fibonacci number for 7 is 13
The Fibonacci number for 11 is 89``````

Code: Select all

``````The Fibonacci number for 5 is 5

The Fibonacci number for 7 is 13

The Fibonacci number for 11 is 89

``````
Check input and AC output for thousands of problems on uDebug!
darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 495 - Fibonacci Freeze

still sir it's WA T_T.... I don't know why my code is WA..... @_@

ok ok hahah I know the problem now... the code just got accepted XD
dotnet12
New poster
Posts: 4
Joined: Fri Aug 17, 2012 9:43 pm

### Re: 495 - Fibonacci Freeze

Can any1 please tell me what is wrong wid dis solution?

#include <stdio.h>

int main()
{
long long int f[5000],in,last=f[0];
int i;

while((scanf( "%lld" , &in))==1)
{

for(i=0;i<=in;i++)
{
f[0]=0,f[1]=1;
f=f[i-1]+f[i-2];
if(f>last)
{
last=f;

}

}
printf("The Fibonacci number for %lld is %lld \n",in,last);
last=0;

}

return 0;
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Code: Select all

``The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125``
Check input and AC output for thousands of problems on uDebug!
sumon sarker
New poster
Posts: 4
Joined: Tue Mar 20, 2012 7:58 am