495 - Fibonacci Freeze
Moderator: Board moderators
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 ?!!?!?!!?!
-
- 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?
I have created an operator to cout bignum and an operator to add two bignum before...
Thank you!
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;
}
}
}
Thank you!
-
- 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!
Re: 495 - Fibonacci Freeze
Hello
Why am I getting Runtime error?
Why am I getting Runtime error?
Code: Select all
import java.io.*;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
Scanner scanner = new Scanner(reader);
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();
}
}
}
-
- 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!
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";
// BufferedReader reader = new BufferedReader(new StringReader(text));
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
Scanner scanner = new Scanner(reader);
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();
}
}
}
-
- 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!
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.
-
- 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!
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?
or maybe if the input of the user is greater than 5000 its gives nothing?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 495 - Fibonacci Freeze
Sample input:Correct output:Your output:
Code: Select all
5
7
11
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!
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
ok ok hahah I know the problem now... the code just got accepted XD
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;
}
#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;
}
-
- 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!
-
- New poster
- Posts: 4
- Joined: Tue Mar 20, 2012 7:58 am
- Location: Dhaka,Bangladesh
- Contact:
Re: 495 - Fibonacci Freeze
The Fibonacci number for 5 is 5
The Fibonacci number for 7 is 13
The Fibonacci number for 11 is 89
The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
But still i am in WA.
Please help me!
The Fibonacci number for 7 is 13
The Fibonacci number for 11 is 89
The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
But still i am in WA.
Please help me!