I tried solve this problem 6 times and 3 of their are WA15,
This WA is expects when uses binsearch, when I replaced type of numbers from long to BigInteger in java, I got AC, in this 15' test intermediate(промежуточные) numbers bigger than 2000000000 or lower than -2000000000, that is why we have wrong answers ))
Good luck!

Edited by author 27.01.2009 21:59

then 15 test incorrect.

I use binsearch and long long in C++, all is ok.
by finding value with BS you can take for example 10^9
and if the previous value is 10^9 then you get the following sequence
10^9, 10^9, 2*10^9, 3*10^9, 5*10^9, and so on.
by overflowing the integer and long types the answer is wrong
I used next hint:
for (.........)
{
....
if (fib[i] > 2*10^9)
fib[i] = 2*10^9 +1;
if (fib[i] < -2*10^9)
fib[i] = -2*10^9 -1;
}

Edited by author 01.06.2010 16:57

Edited by author 01.06.2010 16:57

Thank you very much, it is just the reason why I got a WA at #15.

I tried what you say, but also WA15. I can't understand why??

Well,that was worse....Thanks for hint

Thanks man