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

ranacse05
New poster
Posts: 37
Joined: Wed Mar 28, 2007 5:08 pm
Location: Rajshahi
Contact:

Post by ranacse05 » Sat Apr 14, 2007 12:36 pm

Tell me where is the error?


#include<stdio.h>

int main()
{
int num,a,b,i;
long long unsigned int c;

while(scanf("%d",&num)==1)
{
c=0;a=1;b=1;
for(i=3;i<=num;i++)
{
c=a+b;
a=b;
b=c;
}
printf("The Fibonacci number for %d is %llu\n",num,c);
}
return 0;
}
I like to solve problems.

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Sat Apr 14, 2007 1:15 pm

u must use big integer to solve this problem...
try these:
INPUT:

Code: Select all

5000
OUTPUT:

Code: Select all

The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

Nakar
New poster
Posts: 16
Joined: Tue Apr 17, 2007 6:37 pm

Post by Nakar » Wed Apr 25, 2007 7:58 pm

My output is correct, but in server CE (compile error).

"Compile error". WHY?

Code: Select all

CODE REMOVE

Thanks Jan (for help me with 1st error "compile error").
Please, help.
Last edited by Nakar on Wed Apr 25, 2007 9:22 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Apr 25, 2007 8:12 pm

Replace

Code: Select all

int borrarint(bigint *a)
with

Code: Select all

void borrarint(bigint *a)
Ami ekhono shopno dekhi...
HomePage

Nakar
New poster
Posts: 16
Joined: Tue Apr 17, 2007 6:37 pm

Post by Nakar » Wed Apr 25, 2007 8:18 pm

Now WA, but it is another problem (my problem).

Thanks Jan.


My 2nd error was:

Print fib(0)="" ------> Print fib(0)=0

Now my problem is AC.

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

Post by <:3)~~ » Fri May 18, 2007 9:27 pm

with the fo.llowing code i got a compile error which is running perfectly on my comp.


import java.io.*;
import java.util.*;
import java.math.*;
class Main{
private static BufferedReader stdin =
new BufferedReader( new InputStreamReader( System.in ) );
public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}

void Begin(){
int j,number=0;
String input=null;
while (true) {
try{
input = stdin.readLine();
number = Integer.parseInt( input );
}catch(Exception e){
System.exit(0);
}
BigInteger a = new BigInteger("0");
BigInteger b = new BigInteger("1");
BigInteger c = new BigInteger("0");
for(j=0;j<number;j++)
{
a=b;b=c;
c=a.add(b);
}
System.out.println("The Fibonacci number for "+number+" is "+c);
}
}
}

Here are the compiler error messages:

05593703_24.java:3: Can't find default package `java.math'. Check the
CLASSPATH environment variable and the access to the archives.
1 error

someone plz help.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri May 18, 2007 9:33 pm

Currently UVa's judge doesn't allow to use java.math.BigInteger.
You have to implement bignums yourself.

edit: this is no longer true; judge now uses jdk 1.6.

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

g++: Internal compiler error: program as got fatal signal 25

Post by gba356 » Fri Jun 15, 2007 3:35 pm

I sumitted my code by it gave me CE with error:

g++: Internal compiler error: program as got fatal signal 25

Huh? Signal 25?

Can somebody please help me?

Any help is appreciated^^

Code: Select all


Code removed after accepted with mf's help, thanks!!!

Last edited by gba356 on Sat Jun 16, 2007 1:19 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Jun 15, 2007 3:46 pm

When you use initialized arrays like this:

Code: Select all

#define N 5002
int fab[N][N]={{0}};
the compiler might put the array in the initialized data section, and as a result produce an executable file of size about 100Mb of mostly zero bytes. Probably that's too big for some compiler's module and it crashes with signal 25 (SIGXFSZ, File size limit exceeded).

If you don't initialize it, compiler will put the array in uninitialized data section, memory for which will be allocated at run-time, and then filled with zeros, too - so don't bother initializing globals with 0s.

Anyway, default memory limit for programs is 32Mb at this judge, so your program won't be accepted.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Tue Jul 17, 2007 7:14 am

how much digits the 5000th fibonacci number takes??
what is urs minimum time and memory to solve it??
how is it possible to solve it in 0.00 sec and min mem??




advanced thanx!!






simple, simply the best!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jul 17, 2007 4:52 pm

newton wrote:how much digits the 5000th fibonacci number takes??
1045 digits.
newton wrote:what is urs minimum time and memory to solve it??
I forgot completely.
newton wrote:how is it possible to solve it in 0.00 sec and min mem??
Nobody has solved it in 0.000 seconds.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Aug 02, 2007 11:01 am

There is something unusual with this problem. I created an input file for all numbers between 0 and 5000 inclusive and ran my solution for it. On my PC it worked ~3 seconds. But Judge says it's TLE.
But I managed to get AC (thanking little joey). (His) Hint for PAS programmers: don't use write to output. Output everything in ansistring and then just writeln it.
Now I lay me down to sleep...
my profile

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Post by peterkwan » Sat Nov 03, 2007 8:42 pm

I have written the following code for this problem:

Code: Select all

-- Deleted --
I have tested using the test cases in this thread and found myself correct. However, I submitted to the judge and it says WA. what's wrong with my code?

Thanks.
Last edited by peterkwan on Sun Nov 04, 2007 8:42 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sat Nov 03, 2007 9:03 pm

Try this case..

Code: Select all

5000
4998
4997
See the result of '4997'
I don't know why this is happening..

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Post by peterkwan » Sun Nov 04, 2007 8:42 am

Found my problem already. Thanks.

Post Reply

Return to “Volume 4 (400-499)”