ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1150. Номера страниц

I got it by precalc, but wanna know smart solution
Послано Apkawa 2 май 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
Послано bashNewbie 10 окт 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