## 495 - Fibonacci Freeze

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

Moderator: Board moderators

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

little joey
Guru

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

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

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

Thanks a lot!!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

### 495 TLE

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 ...?
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Eduard
Experienced poster

Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Cache it so you won't keep calculating..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

and what i can du for geting AC this problem.
I wrote it in Pascal.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Eduard
Experienced poster

Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Think about input like

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

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.
Joseph Kurniawan
Experienced poster

Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

### 495 Can't write in PASCAL ?

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 ?
boy_behind_glasses
New poster

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

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).

little joey
Guru

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

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 !
boy_behind_glasses
New poster

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

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

little joey
Guru

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

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
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]
boy_behind_glasses
New poster

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

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'.

little joey
Guru

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

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 ?
boy_behind_glasses
New poster

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

[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
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]
boy_behind_glasses
New poster

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

PreviousNext