|
|
вернуться в форум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). 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 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 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 |
|
|
