Page 8 of 15
Posted: Wed Nov 10, 2004 9:23 am
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
495 Can't write in PASCAL ?
Posted: Wed Nov 17, 2004 2:20 pm
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 ?
Posted: Wed Nov 17, 2004 3:25 pm
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).
Posted: Wed Nov 17, 2004 3:55 pm
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 !
Posted: Wed Nov 17, 2004 5:45 pm
by little joey
Oops. I meant the 5000-th fibo, which has more than 1000 digits too.
Posted: Thu Nov 18, 2004 9:37 am
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]
Posted: Thu Nov 18, 2004 12:30 pm
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'.
Posted: Thu Nov 18, 2004 2:50 pm
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 ?
Posted: Thu Nov 18, 2004 3:01 pm
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]
Posted: Thu Nov 18, 2004 3:10 pm
by boy_behind_glasses
This is my new program, it raise RF
[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
Posted: Fri Nov 19, 2004 10:13 am
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
495 - strange bug!
Posted: Sat Nov 20, 2004 2:20 am
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!
)
(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?
Posted: Sat Nov 20, 2004 6:35 am
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.
Posted: Sat Nov 20, 2004 2:10 pm
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?
Posted: Tue Nov 30, 2004 11:36 am
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