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 1150. Page Numbers

I got it by precalc, but wanna know smart solution
Posted by Apkawa 2 May 2022 11:34
I precalculated digits for segment from 1e5 to 2e5, then i computed all digits from 1 to 1e5(if n >= 1e5), then i stepped from 1e5 to n with step size = 1e5. And after all this I computed digits from last step to n. It does about 1e9/1e5 steps and works 0.015 sec.

I think that it's dumb solution, so I want to know, how to solve this task in O(log10(n)) or smth similar.
Re: I got it by precalc, but wanna know smart solution
Posted by bashNewbie 10 Oct 2023 12:33
Two ways I know -

1) Solve for each number of digits
2) Better way (hint): 1 to 10, 11 to 20, etc. each digit is counted once in the ones place

Edited by author 10.10.2023 12:37

Edited by author 10.10.2023 12:37