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

To all who WA many times but don't know what's wrong
Posted by Ural_Huang Shang 3 Apr 2003 20:45
You must use 'Longint' type in the sequence,
But 'Extended' in the coefficient!

Hope this will be helpful.
Good luck.
I don't think you are right.Seen my program
Posted by Ural_Banyan Tree 7 Apr 2003 18:08
program t1133;
var a1,a2,i1,j1,n,j,i,t1:longint;
    b,x1,y1,t:extended;
    f:array[0..2000]of extended;
    a:array[-2000..2000]of extended;
begin
     readln(i1,x1,j1,y1,n);
     if i1>j1 then begin t1:=i1; i1:=j1; j1:=t1; t:=x1; x1:=y1;
y1:=t; end;
     f[1]:=1; f[2]:=1;
     for i:=3 to j1-i1 do f[i]:=f[i-1]+f[i-2];
     b:=trunc((y1-x1*f[j1-i1-1])/(f[j1-i1]));
     a[i1]:=x1; a[i1+1]:=b;
     if n>i1 then
        for i:=i1+2 to n do
            a[i]:=a[i-1]+a[i-2];
     if n<i1 then
        for i:=i1-1 downto n do
            a[i]:=a[i+2]-a[i+1];
     writeln(a[n]:0:0);
end.




I'm right!
Posted by Ural_Huang Shang 8 Apr 2003 18:56
> program t1133;
> var a1,a2,i1,j1,n,j,i,t1:longint;
>     b,x1,y1,t:extended;
>     f:array[0..2000]of extended;
>     a:array[-2000..2000]of extended;
> begin
>      readln(i1,x1,j1,y1,n);
>      if i1>j1 then begin t1:=i1; i1:=j1; j1:=t1; t:=x1; x1:=y1;
> y1:=t; end;
>      f[1]:=1; f[2]:=1;
>      for i:=3 to j1-i1 do f[i]:=f[i-1]+f[i-2];
>      b:=trunc((y1-x1*f[j1-i1-1])/(f[j1-i1])); (*)
>      a[i1]:=x1; a[i1+1]:=b;
>      if n>i1 then
>         for i:=i1+2 to n do
>             a[i]:=a[i-1]+a[i-2];
>      if n<i1 then
>         for i:=i1-1 downto n do
>             a[i]:=a[i+2]-a[i+1];
>      writeln(a[n]:0:0);
> end.
>
Pay attention that you use 'trunc' in your program (the line
with '*').It is the same as use 'Longint'.
Re: I'm right!
Posted by Ural_Banyan Tree 15 Apr 2003 11:51
f:array[0..2000]of extended;
Pay attention that this must use 'extended';
Do you understand??
Re: I'm right!
Posted by Ural_Huang Shang 18 Apr 2003 19:18
No, it doesn't need to be. Just use Longint, that's OK!
Re: I'm right!
Posted by Ural_Huang Shang 18 Apr 2003 19:24
In array F, you must use 'Extended', but in array A, you MUST
use 'Longint'. In my first saying I meant this!
Re: To all who WA many times but don't know what's wrong
Posted by Ural_Li Zhi 23 Aug 2003 06:46
Oh!
No wonder I always got wrong answer!
Re: I'm right!
Posted by Stupnikov Pavel 31 Mar 2004 21:31
Try to use trunc (((y1-x1*f[j1-i1-1])/(f[j1-i1]))+1e-6).
Whats Wrong? WA10
Posted by Uran 22 Mar 2007 23:02
#include <iostream.h>
#include <iostream>
long p(long q)
{return (q+1000);}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
    long double  a[2002];
    long double  c[2002];
    long double  x[2002];
    long i,j,n,t;
    for (t=0;t<2002;t++){a[t]=c[t]=x[t]=0;}
    cin>>i;
    cin>>a[p(i)];
    cin>>j;
    cin>>a[p(j)]>>n;
    if (i>j)
    {
    t=i;
    i=j;
    j=t;
    }//i<j
    c[p(i)]=1;x[p(i)]=0;
    c[p(i+1)]=0;x[p(i+1)]=1;
    for (t=i+2;t<j+1;t++){c[p(t)]=c[p(t-1)]+c[p(t-2)];x[p(t)]=x[p(t-1)]+x[p(t-2)];}
    a[p(i+1)]=a[p(j)]/x[p(j)]-c[p(j)]/x[p(j)]*a[p(i)];
    if (i<=n)
    {
        for (t=i+2;t<n+1;t++)
        {a[p(t)]=a[p(t-1)]+a[p(t-2)];}
    }
    if (i>n)
    {
        for (t=i-1;t>n-1;t--){a[p(t)]=a[p(t+2)]-a[p(t+1)];}
    }
    cout<<(long)a[p(n)];
    return 0;
}
Re: I'm right!
Posted by partisan (Andrey Korotkov) 10 Nov 2007 16:14
Use round! When integers will be <0, trunc(-1+1e-6) will be equals to 0!

Edited by author 10.11.2007 16:44
No subject
Posted by cpc 10 Nov 2007 16:42


Edited by author 10.11.2007 16:47