495 - Fibonacci Freeze

[Ahmad]

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]

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]

Precompute.

[sith]

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) {

     
        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();
        }
    }
}

[brianfry713]

Try input 5000

[sith]

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();
        }
    }
}

[brianfry713]

Try input 5000

[darksk4]

Why is this a WA?

Code: Select all

Code Accpeted

[brianfry713]

Don't print blank lines in the output.

[darksk4]

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]

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

Your 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

[darksk4]

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]

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]

Code: Select all

The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

[sumon sarker]

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!