A HINT

Posted by

Jorjia 18 Jan 2018 15:49

Solution is a sum( [ sqrt(2*i*R - i^2) ], i = 1,2,...,R), where [ x ] - round to up.

But, I always GOT TL on 17 test).

Re: A HINT

if we notice f(i)==sqrt(2*i*R-i*i); and f(i+1)-f(i) always >=sqrt(R)

we can change to count howmany i satisfy c==sqrt(2*i*R-i*i) then answer+=ways*c

then this problem will be solved in O(sqrt(R))

thank you for your hint

Re: A HINT

my fault but increment of f(i) seems to be monotonic decreasing and increment <=sqrt(2*r)

so we can binary search and divide them to sqrt(2*r) segment with same increment and add each segment using sum of arithmetic series

Re: A HINT

my fault but increment of f(i) seems to be monotonic decreasing and increment <=sqrt(2*r)

so we can binary search and divide them to sqrt(2*r) segment with same increment and add each segment using sum of arithmetic series