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}.

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