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

wa15
Posted by 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?
Re: wa15
Posted by Denis Koshman 9 Sep 2008 23:50
My AC solution replies 1. I don't know if this test is correct as I solved this problem loooong ago.
Re: wa15
Posted by Sandello 1 Nov 2008 04:05
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
Re: wa15
Posted by Erko 3 Jan 2009 19:03
i use binsearch and have wa 15..
any hints plz
Re: wa15
Posted by Petar 1 Apr 2011 15:09
The sequence is {1 0 1 0 1}

Edited by author 01.04.2011 15:39
Re: wa15
Posted by Tranvick 31 Jan 2012 14:53
It's wrong. If f[2]=0, the sequence is {1 0 1 1 2}.
Re: wa15
Posted by 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.
Re: wa15
Posted by Chitanda Eru 4 Nov 2013 22:07
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.
Re: wa15
Posted by Leonid 5 Nov 2013 18:43
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