495 - Fibonacci Freeze

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 495 - Fibonacci Freeze

Post by Ahmad » Sun Jul 10, 2011 10:38 pm

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

Post by kia.masster » Sun May 20, 2012 4:42 pm

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

Post by brianfry713 » Sun May 20, 2012 9:15 pm

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

Post by sith » Fri Jul 20, 2012 4:29 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 495 - Fibonacci Freeze

Post by brianfry713 » Fri Jul 20, 2012 9:24 pm

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

Post by sith » Thu Jul 26, 2012 4:16 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 495 - Fibonacci Freeze

Post by brianfry713 » Fri Jul 27, 2012 1:15 am

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

Post by darksk4 » Sun Jul 29, 2012 7:13 pm

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

Post by brianfry713 » Mon Jul 30, 2012 11:06 pm

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

Post by darksk4 » Tue Jul 31, 2012 5:59 pm

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

Post by brianfry713 » Wed Aug 01, 2012 3:16 am

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

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

Post by darksk4 » Wed Aug 01, 2012 7:36 am

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

Post by dotnet12 » Sat Aug 18, 2012 5:59 pm

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

Post by brianfry713 » Mon Aug 20, 2012 10:21 pm

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
Location: Dhaka,Bangladesh
Contact:

Re: 495 - Fibonacci Freeze

Post by sumon sarker » Sat Aug 25, 2012 4:59 am

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!

Post Reply

Return to “Volume 4 (400-499)”