| Show all threads Hide all threads Show all messages Hide all messages | | Page 2 | | Java BigInteger can also be useful here.... | Nisarg Shah | 1133. Fibonacci Sequence | 13 Dec 2008 11:25 | 1 | As mentioned in the previous topic, we just need to store 1/fib(n) and fib(n-1)/fib(n) because fib(i+1)=fib(j)/fib(j-i) - (fib(j-i-1)/fib(j-i))*fib(i) . But I used Java BigInteger to store fib(n) instead of the fractions to maintain precision and it got AC. | | Help! WA 16. Here my code. | Iosif inf-10 | 1133. Fibonacci Sequence | 6 Nov 2008 13:23 | 1 | Var
i,j,n,Fi,Fj:longint;
Fi1,Fn:extended;
k:integer;
F:array[-2001..2001] of extended;
Begin
Readln(i,Fi,j,Fj,n);
F[0]:=0; F[1]:=1;
for k:=2 to 2001 do
F[k]:=F[k-1]+F[k-2];
for k:=-1 downto -2001 do
F[k]:=F[k+2]-F[k+1];
Fi1:=((Fj-F[j-i-1]*Fi)/F[j-i]);
Fn:=(F[n-i]*Fi1+F[n-i-1]*Fi);
writeln(round(Fn));
End.
Why WA#16?
Edited by author 06.11.2008 13:26 | | wa15 | Experimenter | 1133. Fibonacci Sequence | 5 Nov 2013 18:43 | 9 | wa15 Experimenter 9 Sep 2008 21:04 i use binsearch and have wa 15..
i found this test
1 1 5 1 2
what's answer? is this test correct? My AC solution replies 1. I don't know if this test is correct as I solved this problem loooong ago. this test is incorrect because answer for it is -(1/3), it's not integer number
1st elem - 1
2nd elem - -1/3
3rd elem - 2/3
4th elem - 1/3
5th elem - 1
Edited by author 01.11.2008 04:06 i use binsearch and have wa 15..
any hints plz About this test {1 1 5 1 2} case the answer is also 0.
The sequence is {1 0 1 0 1}
Edited by author 01.04.2011 15:39 It's wrong. If f[2]=0, the sequence is {1 0 1 1 2}. Re: wa15 Alexey Dergunov [Samara SAU] 15 May 2012 23:02 How to avoid WA 15
While calculating f[n] during another iteration of binary search, every time check if f[i] is out of [-2*10^9, 2*10^9]. If it is, immediately break calculation cycle, update binary search interval and start another its iteration. I used formula and a C++ type long long, but still somehow managed to get WA 15. Even though i got around it by calculating in Zp (where p is a prime number bigger than 4 * 10^9), it still blows up my mind how it's possible to overflow long long without violating the statement. Such a tricky test, i'd like to see it. Some tests:
test: -36 1680987685 37 1439530908 1
ans: 12
test: 42 1330344015 -38 -1330344015 30
ans: 4131543
test: -459 0 245 0 999
ans: 0
Edited by author 05.11.2013 18:43
Edited by author 05.11.2013 18:47 | | I solve recurrence equation by using characteristic equation | BigBin | 1133. Fibonacci Sequence | 4 Sep 2008 14:13 | 2 | I solve recurrence equation by using characteristic equation
F(n) = c1*pow(Phi, n) + c2*pow(phi, n); by
c2 = ( fp*pow(Phi, q) - fq*pow(Phi, p) )/( pow(Phi, q)*pow(phi, p) - pow(Phi, p)*pow(phi, q) );
c1 = ( fq - c2*pow(phi, q) ) / pow(Phi, q);
i use long double to keep and round the answer but i got WA in test case 12. Anyone can help me please? | | WA#16, i think my algo is correct | Bobur | 1133. Fibonacci Sequence | 9 Apr 2008 18:28 | 1 | var
min, i, j, n, fi, fj, fn : integer;
x1, y1, x, y, min1 : extended;
k : integer;
begin
read(i, fi, j, fj, n);
min := i;
if min > j then
begin
i := j;
j := min;
min := fi;
fi := fj;
fj := min;
end;
if n < i then
begin
x := 1; y := 0;
for k := 1 to i-n do
begin
min1 := x;
x := x + y;
y := min1;
end;
x1 := 1; y1 := 1;
for k := 1 to j-n do
begin
min1 := x1;
x1 := x1 + y1;
y1 := min1;
end;
fn := TRUNC((fj*y-fi*y1)/(x1*y+x*y1));
end
else
begin
x := 1; y := 0;
for k := 1 to n-i do
begin
min1 := x;
x := x + y;
y := min1;
end;
x1 := 1; y1 := 0;
for k := 1 to j-i do
begin
min1 := x1;
x1 := x1 + y1;
y1 := min1;
end;
fn := TRUNC(((fj-x1*fi)*y)/y1+x*fi);
end;
writeLn(fn);
end.
pls, help me!!
Edited by author 09.04.2008 20:26 | | test data | lian lian | 1133. Fibonacci Sequence | 3 Jan 2008 21:21 | 2 | who could give me test data of "1133"? who could mail code to me?
my e_mail :k13795263@gmail.com | | WHY I GET WA ON TEST 10.. | Ghost | 1133. Fibonacci Sequence | 7 May 2009 06:51 | 2 | IF YOU KNOW , CAN U CONTACT WITH ME ..
MY EMAIL IS ZELIN.HE@GMAIL.COM
THX..
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
long double f1[2001],f2[2001];
int main()
{
int x , y , fx , fy , n ;
double fn;
scanf("%d%d%d%d%d",&x,&fx,&y,&fy,&n);
f1[0] = 1 ; f1[1] = 0 ;
f2[0] = 0 ; f2[1] = 1 ;
if ( x > y )
{
int tmp = x ;
x = y ;
y = tmp ;
tmp = fx;
fx = fy;
fy = tmp;
}
int k ;
int i;
for ( i=x+2; i <= y ; i ++ )
{
if ( x < 0 ) k = -x + i;
else k = i - x;
f1[k] = f1[k-1]+f1[k-2];
f2[k] = f2[k-1]+f2[k-2];
}
long double b = ceil(fy-f1[y-x]*fx)/(f2[y-x]);
long double a = fx;
long double c;
if ( x+2 <= n )
{
for ( i = x+2 ; i <= n ; i ++ )
{
c = a + b ;
a = b ; b = c ;
}
printf("%.0llf\n",c);
}
else
{
if (x == n ) printf("%.0llf\n",a);
else if ( n == x + 1 ) printf("%.0llf\n",b);
else
{
for (i = x ; i > n ; i -- )
{
c = b - a ;
b = a ; a = c;
}
printf("%.0llf\n",c);
}
}
system("PAUSE");
return 0;
} I did similarly in C++ and was getting WA on #10. Later, I wrote the same solution in Java (with BigInteger) and worked. | | Help me please, WA 11. | Denis | 1133. Fibonacci Sequence | 9 Apr 2008 18:44 | 2 | Finally I've found my bug...
Be careful while doing binary search. My problem was that I couldn't find right bounds for it. Then I wrote:
l = 0;
r = 4000000000;
and in the function, which returns possibilit of such element I did such thing:
vl -= 2000000000;
I think, it'll be helpful for someone!
Edited by author 17.11.2007 01:46 i don't use binary search.
i did it with maths, and DP.
but i've WA#11, pls help,
here is my code!!!
var
min, i, j, n, fi, fj, fn, x, y, x1, y1 : int64;
k : integer;
begin
read(i, fi, j, fj, n);
min := i;
if min > j then
begin
i := j;
j := min;
min := fi;
fi := fj;
fj := min;
end;
if n < i then
begin
x := 1; y := 0;
for k := 1 to i-n do
begin
min := x;
inc(x, y);
y := min;
end;
x1 := 1; y1 := 1;
for k := 1 to j-n do
begin
min := x;
inc(x1, y1);
y1 := min;
end;
fn := TRUNC((fj*y-fi*y1)/(x1*y+x*y1));
end
else
begin
x := 1; y := 0;
for k := 1 to n-i do
begin
min := x;
inc(x, y);
y := min;
end;
x1 := 1; y1 := 0;
for k := 1 to j-i do
begin
min := x1;
inc(x1, y1);
y1 := min;
end;
fn := TRUNC(((fj-x1*fi)*y)/y1+x*fi);
end;
writeLn(fn);
end.
if you know my mistake, pls help me!!!
thanks a lot | | Pascal or C/C++ (extended && double) | St.Max [UPML KNU] | 1133. Fibonacci Sequence | 10 Jan 2008 19:03 | 2 | I work using C++.
But on this problem I saw that for my algorithm it is not enough double and long double. And only pascal's extended gave me this AC. That's because double has about 340 in exponent, and long double not in all compilers have 12 bytes, sometimes long double=double | | Just use binary search in the range (-2000000000 , 2000000000) to find the second number! | shrek | 1133. Fibonacci Sequence | 7 Nov 2006 12:09 | 1 | | | coping with accuracy | Todor Tsonkov | 1133. Fibonacci Sequence | 21 Mar 2007 16:35 | 3 | To all c++ coders who've made this problem, how did you cope with accuracy ? I couldn't cope with this problem using C++.
So... I used pascal...
THE SAME CODE GAVE ME AC
Edited by author 19.03.2007 18:46
Edited by author 19.03.2007 18:46 Use binsearch and you'll not need to cope with accuracy. And I couldn't solve it in Pascal using other algo... | | Re: why compilation error? | Tabledott | 1133. Fibonacci Sequence | 7 Jul 2006 01:41 | 3 | [code deleted]
Just wanna say it works pretty well on my mashine ;)
Edited by author 14.06.2006 02:24
Edited by moderator 14.06.2006 16:24 Replace
sqrt(5)
with
sqrt(5.)
or
sqrt( double( 5 ) )
because there is an ambiguilty, what type to the compiler should convert an integer. Yup, 10x, you`re right. Btw, to all c++ coders who've made this problem, how did you cope with accuracy ? | | test 16 | Trần Quang Chung | 1133. Fibonacci Sequence | 6 Jun 2006 06:20 | 1 | test 16 Trần Quang Chung 6 Jun 2006 06:20 I'm WA test#16. Anybody have test#16. Help me! | | AC at last | AlexF | 1133. Fibonacci Sequence | 1 Nov 2008 04:12 | 2 | That is a good problem!
Edited by author 06.05.2006 19:25
Edited by author 06.05.2006 19:26 i agree with you, it's very nice =) | | WA AGAIN!!! I'm sure in my code, BUT .... | Akshin Salimov | 1133. Fibonacci Sequence | 5 Jan 2006 20:05 | 1 | var
i,j,ii,n,imin,imax,fs,fo,sfs1,sfs2,sfo1,sfo2,xx:longint;
a,b,c:longint;
f:array[-1000..1000] of longint;
procedure readdata;
begin
readln(i,f[i],j,f[j],n);
if i=n then
begin
writeln(f[i]);
halt;
end;
if j=n then
begin
writeln(f[j]);
halt;
end;
end;
begin
readdata;
if abs(j-i)>1 then
begin
if i<j then
begin
imin:=i;
imax:=j;
end else
begin
imin:=j;
imax:=i;
end;
ii:=imin+2; fs:=0; fo:=0;
sfs1:=1; sfs2:=0;
sfo1:=0; sfo2:=1;
while (ii<=imax) do
begin
fs:=sfs1+sfs2;
sfs2:=sfs1;
sfs1:=fs;
fo:=sfo1+sfo2;
sfo2:=sfo1;
sfo1:=fo;
inc(ii);
end;
fo:=fo*f[imin];
xx:=(f[imax]-fo) div fs;
end else xx:=f[imax];
if n=imin+1 then
begin
writeln(xx);
halt;
end;
a:=f[imin]; b:=xx;
if n>imin then
for ii:=imin+2 to n do
begin
c:=a+b;
a:=b;
b:=c;
end else
for ii:=imin-1 downto n do
begin
c:=b-a;
b:=a;
a:=c;
end;
writeln(c);
end. | | Hint | ftc | 1133. Fibonacci Sequence | 18 Jul 2005 23:54 | 1 | Hint ftc 18 Jul 2005 23:54 If you write on C++, when storing coefficients you can use long double instead of double, and then you can get AC. | | Funny solution | Samsonov Alex [SESC USU] | 1133. Fibonacci Sequence | 5 Jul 2005 12:44 | 1 | I got AC in C++ using binary search... Of course, I had to use int64 to check whether all the nums are less than 2000000000, but it's easy enough... There is no problem with TL because abs(i,j)<=1000... | | I've passed 1133 using c++ | BFL | 1133. Fibonacci Sequence | 29 May 2005 14:34 | 1 | my idea :
typical sequence
i 1 2 3 4 5 6 7
fib(i) 1 1 2 3 5 8 13
assume that i<=j
first, we have to find f(i+1)
diff=j-i
using F(i+1)=Fj/fib(diff) - Fi*fib(diff-1)/fib(diff)
but my prog didn't compute fib(i) but only computed
1/fib(i) and fib(i-1)/fib(i)
using formular
1/fib(i) = 1/(1/fib(i-1)+1/fib(i-2))
double f1(int ind)// return 1/fib(ind)
{
int i;
double a[3]={1,1};
for(i=2;i<ind;i++)
a[i%3]=1/(1/a[(i+1)%3]+1/a[(i+2)%3]);
return a[(ind -1)%3];
}
fib(i-1)/fib(i) using this relation
1+1/(1+1/(1+1/...))
double f2(int ind)// return fib(ind-1)/fib(ind)
{
int i;
double ret=1;
for(i=0;i<ind-2;i++)
ret=1/(ret+1);
return ret;
}
using this procedure, we can store any computation with
double and avoid int overflow.
and so the F(i+1) = (Fj*f1(diff)-Fi*f2(diff)), then find f(n) with ordinary algo using int(it said that fk can store in INT) !! | | help plz | Muhammet | 1133. Fibonacci Sequence | 22 May 2005 11:05 | 1 | would you mind helping?
what is test 9
I got WA on test case 9 | | Who solve this problem on C? Please give hint, why wrong 9? | Lifanov | 1133. Fibonacci Sequence | 12 Apr 2005 13:31 | 1 | #include <stdio.h>
#include <math.h>
int i,j,Fi,Fj,n;
int main(){
//freopen("in.txt","r",stdin);
scanf("%d%d%d%d%d",&i,&Fi,&j,&Fj,&n);
int t,k;
if(i>j){
t=i;
i=j;
j=t;
t=Fi;
Fi=Fj;
Fj=t;
}
// i < j
j-=i;
n-=i;
i=0;
// 0 j n
double f1=0.0,f2=1.0,f,tempf;
f=f1+f2;
for( k=1;k<j;k++){
f=f1+f2;
f1=f2;
f2=f;
}
//printf("%.0lf\n",f);
double F0=Fi;
double F1=floor((Fj-f1*F0)/f);
//printf("%.0lf\n",F1);
f1=F0;
f2 =F1;// modf(F1,&f2);
if(n>0){
for(k=1;k<n;k++){
f=f1+f2;
f1=f2;
f2=f;
}
f=f2;
}
else{
for(k=-1;k>n;k--){
f=f2-f1;
f2=f1;
f1=f;
}
f=f2;
}
printf("%.0lf",f);
return 0;
}
Edited by author 12.04.2005 13:48 |
|
|
