495 - Fibonacci Freeze

[little joey]

Using write to produce output in pascal is extremely slow. Assemble all output for one line in an ansistring and do one writeln.

Change
[pascal] for n := k[i] downto 1 do
write(ans[i,n]);
writeln;[/pascal]
To
[pascal] setlength(line,k[i]);
for n := k[i] downto 1 do
line[k[i]-n+1]:=chr(ans[i,n]+ord('0'));
writeln(line); [/pascal]
where var line:ansistring;

That way you'll get AC in less than a second!

PS: please remove your code now, 'cause it's a spoiler

[Observer]

(......I've never thought of that.......)

WOW!!!!!!!!!! It works!!!!!!




Thanks a lot!!!!

[Eduard]

can someone help me i got time limit exceeded in problem 495(fibonachi).
my program is rigth and it works 1second when n=5000 i thing i'm doing
something wrong with input.is this problem input while not eof or ...?

[Larry]

Cache it so you won't keep calculating..

[Eduard]

and what i can du for geting AC this problem.
I wrote it in Pascal.

[Dominik Michniewski]

Think about input like

5000 (hundred time)
...
4999 (hundred time)
...
and so on ...

Best regards
DM

[Joseph Kurniawan]

Make a function to calculate and store the fibonacci number 0-5000 before running the main function. With this technique, the main function will only have to output the stored fibo number!!
Good luck!!

[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]

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]

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]

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

[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][i]+a[y][i]+nho;
nho:=so div 10;
so:=so mod 10;
a[z][i]:=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[i]=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]

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]

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 ?

[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][i]+a[y][i]+nho;
nho:=so div 10;
so:=so mod 10;
a[z][i]:=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[i]=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]