ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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
  readln(x,fx,y,fy,n);
  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]:=1;c2[1]:=0;
  c1[2]:=0;c2[2]:=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

Correct answer is 1134903170, but your program outputs 1073741824.
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