ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1798. Fire Circle. Version 2

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
Posted by Shen Yang 13 Apr 2018 13:26
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
Posted by Shen Yang 13 Apr 2018 14:08
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
Posted by Shen Yang 13 Apr 2018 14:08
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