wa15

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

My AC solution replies 1. I don't know if this test is correct as I solved this problem loooong ago.

Re: wa15

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

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*

Re: wa15

It's wrong. If f[2]=0, the sequence is {1 0 1 1 2}.

Re: wa15

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

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*