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

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by wirjawan »

try to change

[java]
static int main()
[/java]

to

[java]
public static void main( String [] args )
[/java]

and

[java]
else if( n < 0 ) return 0;
[/java]

to

[java]
else if( n < 0 ) return ;
[/java]

this will at least let your code to run on OJ ( i believe ) ; )

hope this helps :)
..

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

495 Can't write in PASCAL ?

Post by boy_behind_glasses »

I saw many topics in this box about that problem, and all of them are written in C/C++/Java, so they can define a bigint type ( an 1000-digits array )

But in PASCAL, I can't define any array like that:

type bigint = array[1..1000] of byte;
var a:array[0..5000] of bigint;

this code raise "too many variables" error !


so anybody have solution to solve this problem ?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

1. Neither C nor C++ has built in bigint types (don't know about JAVA).
2. 5000! has more than 1000 digits.
3. Get another compiler. I would recommend fpc, the same one the judge is using. It can allocate as much memory and as many variables as you need (although the judge usually limits your memory to 32 Meg, more than enough for this problem).

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

Post by boy_behind_glasses »

little joey wrote:1. Neither C nor C++ has built in bigint types (don't know about JAVA).
2. 5000! has more than 1000 digits.
3. Get another compiler. I would recommend fpc, the same one the judge is using. It can allocate as much memory and as many variables as you need (although the judge usually limits your memory to 32 Meg, more than enough for this problem).
ya, but this problem is to find the n-fibonacci !

I still want to try TP, because of using FPC !

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Oops. I meant the 5000-th fibo, which has more than 1000 digits too.

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

Post by boy_behind_glasses »

Why I got WA in this code:

[pascal]
type bigint=array[1..1500] of byte;
var skt:array[0..5000] of word;
a:array[0..5000] of bigint;
max,i,j,n:word;
procedure cong(x,y,z:word);
var i:integer;
nho:byte;
so:byte;
max:byte;
begin
fillchar(a[z],sizeof(a[z]),0);
nho:=0;
max:=((skt[x]+skt[y])+abs(skt[x]-skt[y])) div 2;
for i:=1 to max do
begin
so:=a[x]+a[y]+nho;
nho:=so div 10;
so:=so mod 10;
a[z]:=so;
end;
skt[z]:=max;
if nho>0 then
begin
inc(skt[z]);
a[z,skt[z]]:=nho;
end;
end;
begin
fillchar(a,sizeof(a),0);
fillchar(skt,sizeof(skt),0);
skt[0]:=1; skt[1]:=1;
a[0][1]:=1; a[1][1]:=1;
max:=1;
n:=1;
while n<>0 do
begin
read(n);
if n=0 then break;
if skt[n]=0 then
for i:=max to n do
if skt=0 then cong(i-1,i-2,i);
if n>max then max:=n;
for j:=skt[n] downto 1 do write(a[n,j]);
writeln;
end;
end.
[/pascal]

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Your program's output for the sample input doesn't match the sample output (off by one) and should contain the whole phrase "The Fibonacci number for ... is ...'.
It prints only spaces for big values of n. Zero (0) is a valid input and your program shouldn't stop but print 'The Fibonacci number for 0 is 0'.

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

Post by boy_behind_glasses »

little joey wrote:Your program's output for the sample input doesn't match the sample output (off by one) and should contain the whole phrase "The Fibonacci number for ... is ...'.
It prints only spaces for big values of n. Zero (0) is a valid input and your program shouldn't stop but print 'The Fibonacci number for 0 is 0'.
http://online-judge.uva.es/p/v4/495.html

Read the problem again, plz !

Even I add this line:
write('The Fibonacci number for ',n,' is ',);


It still get WA ? :cry:

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

Post by boy_behind_glasses »

[pascal]type bigint=array[1..1500] of byte;
var skt:array[0..5000] of word;
a:array[0..5000] of bigint;
max,i,j,n:word;
procedure cong(x,y,z:word);
var i:integer;
nho:byte;
so:byte;
max:byte;
begin
fillchar(a[z],sizeof(a[z]),0);
nho:=0;
max:=((skt[x]+skt[y])+abs(skt[x]-skt[y])) div 2;
for i:=1 to max do
begin
so:=a[x]+a[y]+nho;
nho:=so div 10;
so:=so mod 10;
a[z]:=so;
end;
skt[z]:=max;
if nho>0 then
begin
inc(skt[z]);
a[z,skt[z]]:=nho;
end;
end;
begin
fillchar(a,sizeof(a),0);
fillchar(skt,sizeof(skt),0);
skt[0]:=1; skt[1]:=1;
a[0][1]:=1; a[1][1]:=1;
max:=1;
n:=1;
while n<>0 do
begin
read(n);
if n=0 then break;
if skt[n]=0 then
for i:=max to n do
if skt=0 then cong(i-1,i-2,i);
if n>max then max:=n;
write('The Fibonacci number for ',n,' is ');
for j:=skt[n] downto 1 do write(a[n,j]);
writeln;
end;
end.[/pascal]

boy_behind_glasses
New poster
Posts: 6
Joined: Tue Oct 05, 2004 7:34 am

Post by boy_behind_glasses »

This is my new program, it raise RF :cry: :cry: :cry:
[pascal]
type bigint=array[1..1500] of byte;
var skt:array[0..5000] of word;
a:array[0..5000] of bigint;
max,i,j,n:word;
procedure cong(x,y,z:word);
var i:integer;
nho:byte;
so:byte;
max:byte;
begin
fillchar(a[z],sizeof(a[z]),0);
nho:=0;
max:=((skt[x]+skt[y])+abs(skt[x]-skt[y])) div 2;
for i:=1 to max do
begin
so:=a[x]+a[y]+nho;
nho:=so div 10;
so:=so mod 10;
a[z]:=so;
end;
skt[z]:=max;
if nho>0 then
begin
inc(skt[z]);
a[z,skt[z]]:=nho;
end;
end;
begin
fillchar(a,sizeof(a),0);
fillchar(skt,sizeof(skt),0);
skt[0]:=1; skt[1]:=1;
a[0][1]:=1; a[1][1]:=1;
max:=1;
while not seekeof do
begin
read(n);
if skt[n]=0 then
for i:=max to n do
if skt=0 then cong(i-1,i-2,i);
if n>max then max:=n;
write('The Fibonacci number for ',n,' is ');
for j:=skt[n] downto 1 do write(a[n,j]);
writeln;
end;
end.
[/pascal]

Plz solve this for me :cry: :cry: :cry:

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Consider this input

Code: Select all

0
1
2
5
10
20
50 
100
200
500
1000
2000
5000
Your program gives

Code: Select all

The Fibonacci number for 0 is 1
The Fibonacci number for 1 is 1
The Fibonacci number for 2 is 2
The Fibonacci number for 5 is 8
The Fibonacci number for 10 is 89
The Fibonacci number for 20 is 10946
The Fibonacci number for 50 is 20365011074
The Fibonacci number for 100 is 573147844013817084101
The Fibonacci number for 200 is 453973694165307953197296969697410619233826
The Fibonacci number for 500 is 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626
The Fibonacci number for 1000 is 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
The Fibonacci number for 2000 is 
The Fibonacci number for 5000 is 
The correct output is

Code: Select all

The Fibonacci number for 0 is 0
The Fibonacci number for 1 is 1
The Fibonacci number for 2 is 1
The Fibonacci number for 5 is 5
The Fibonacci number for 10 is 55
The Fibonacci number for 20 is 6765
The Fibonacci number for 50 is 12586269025
The Fibonacci number for 100 is 354224848179261915075
The Fibonacci number for 200 is 280571172992510140037611932413038677189525
The Fibonacci number for 500 is 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
The Fibonacci number for 1000 is 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
The Fibonacci number for 2000 is 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
The Fibonacci number for 5000 is 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

.pandre.
New poster
Posts: 9
Joined: Mon Nov 08, 2004 10:58 pm
Location: Coimbra, Portugal

495 - strange bug!

Post by .pandre. »

hello everyone!

my program generates correct input only untill the 93rd Fibo number... check this out:
...
The Fibonacci number for 92 is 7540113804746346429 (OK)
The Fibonacci number for 93 is 12200160415121876738 (OK)
The Fibonacci number for 94 is 19740274219868223168 (WRONG! :o)
(the correct 94th Fibo number=19740274219868223167...)

my program uses an long double array[5001], in which I put the 5000 first Fibo numbers, then I simply printf("The Fibonacci number for %d is %.0Lf\n",n ,array[n])

can someone explain me what's happening?

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek »

the long double has a fixed precision and range. the %.0Lf will truncate the
value of the argument. so if the variable contained say (1.9999) then %.0Lf will print only 1.

for this problem you have to write you own addition routines.

.pandre.
New poster
Posts: 9
Joined: Mon Nov 08, 2004 10:58 pm
Location: Coimbra, Portugal

Post by .pandre. »

abishek wrote:the long double has a fixed precision and range. the %.0Lf will truncate the
value of the argument. so if the variable contained say (1.9999) then %.0Lf will print only 1.

for this problem you have to write you own addition routines.

but if i remove the .0 I get:

The Fibonacci number for 92 is 7540113804746346429.000000 (OK)
The Fibonacci number for 93 is 12200160415121876738.000000 (OK)
The Fibonacci number for 94 is 19740274219868223168.000000 (still WRONG! )

I think there's no precision problem, but why does it print the wrong number? I'm not sure if the problem is in the printf, maybe it is in the sum of those two big numbers...
:(
I don't understand, can someone help me?

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

Post by randomtaiwanese »

pity those using java...
java does have bigint, but the UVA java stoneage compiler does not support it
btw... the fibonacci number for 500 is 1046 digits

Post Reply

Return to “Volume 4 (400-499)”