ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1133. Fibonacci Sequence

My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
It works like this:
f1=1*f1+0*f2;
f2=0*f1+1*f2;
f3=1*f1+1*f2;
f4=1*f1+2*f2;
f5=2*f1+3*f2;
f6=3*f1+5*f2;
...^....^
...|....These coefficients are in the array c2
...These coefficients are in the array c1

----PROG BELOW----
program ural1133;
const
maxn=2001;
var
c1,c2:array[1..maxn]of extended;
x,y,n,i:integer;
fx,fy,f1,f2:longint;
function min(a,b:integer):integer;
begin
if a<b then min:=a else min:=b;
end;
function max(a,b:integer):integer;
begin
if a>b then max:=a else max:=b;
end;
begin
i:=min(min(x,y),n);
if i<=0 then begin
i:=1-i;
inc(x,i);inc(y,i);inc(n,i);
end;

c1:=1;c2:=0;
c1:=0;c2:=1;
for i:=3 to max(max(x,y),n) do begin
c1[i]:=c1[i-2]+c1[i-1];
c2[i]:=c2[i-2]+c2[i-1];
end;

f1:=round((fx*c2[y]-fy*c2[x])/(c1[x]*c2[y]-c1[y]*c2[x]));
f2:=round((fx*c1[y]-fy*c1[x])/(c2[x]*c1[y]-c2[y]*c1[x]));
writeln(round(c1[n]*f1+c2[n]*f2));
end.
Re: My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
Posted by UNKNOWN_LAMER 16 Feb 2005 00:38
Try this:

46 1836311903 -46 -1836311903 45

Re: My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
Posted by blue_maple 6 May 2007 11:27
I have the same problem. Can anybody help?
No subject
Posted by partisan (Andrey Korotkov) 10 Nov 2007 16:22

Edited by author 10.11.2007 16:27
Re: My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
Posted by partisan (Andrey Korotkov) 10 Nov 2007 16:31
>> writeln(round(c1[n]*f1+c2[n]*f2));
For example c1[n]*f1 may exceed extended (c1[n]*f1+c2[n]*f2 don't, but you will lost correctness), and as I understand, test from UNKNOWN LAMER (thanks!), makes it true

Edited by author 10.11.2007 16:33
Re: My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
Posted by claire_ 11 Nov 2009 11:51
that's true,thanks
Re: My prog deals with coefficients, but WA on test #16. Can anybody help me or gimme that test?
Posted by Edric Mao 31 Aug 2010 21:06
i use round an correct