ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1798. Fire Circle. Version 2

This task is driving me crazy
Posted by Zergatul 7 Apr 2021 02:32
I've implemented several approaches, ones calculate 1/4 of circle, another ones calculate 1/8 of circle. All of them works fine for R < 60000000. With R > 60millions there is a chance (and it increases with bigger R) 2 approaches can give different results. They use the same calculations (sqrt, ceiling). I also tried to implement 1/8 without float point numbers, by integers only. Same result with same difference. Maybe these "magic" numbers can help someone

r: 67250001 correct: 14208049816923164 diff: 12
r: 67250051 correct: 14208070944129524 diff: 4
r: 67250211 correct: 14208138551359320 diff: 4
r: 67250249 correct: 14208154608083608 diff: 8
r: 67250321 correct: 14208185031387396 diff: 16
r: 67250433 correct: 14208232356606236 diff: 4
r: 67250449 correct: 14208239117361224 diff: 4
r: 67250505 correct: 14208262780007696 diff: 4
r: 67250601 correct: 14208303344588340 diff: 8
r: 67250697 correct: 14208343909213316 diff: 4
r: 67250769 correct: 14208374332717888 diff: 4
r: 67250825 correct: 14208397995480888 diff: 4
r: 67250835 correct: 14208402220968636 diff: 4
r: 67251315 correct: 14208605045441340 diff: 8
r: 67251347 correct: 14208618567139620 diff: 12
r: 67251457 correct: 14208665047975948 diff: 4

Edited by author 07.04.2021 02:35
Re: This task is driving me crazy
Posted by Zergatul 8 Apr 2021 01:51
Forget about what I said earlier. It is always good idea to return to the problem with fresh mind :)
It turned out my correct solution was actually incorrect, and my incorrect solutions were correct.
If you are using sqrt and ceil, try to calculate ceil(sqrt(2 * 63611501 * 67250001 - 63611501 * 63611501)), and you will get wrong result
I was able to get AC C# solution with 467286474 int64 multiplications for R=10^9, no divisions, and no floating point usage.

Edited by author 08.04.2021 01:53

Edited by author 08.04.2021 01:53