e-olymp 7228. Сколько шестерок?

Задача

Сколько раз будет использована цифра $6$, если записать подряд последовательные натуральные числа от $a$ до $b$?

Входные данные

Два натуральных числа $a$ и $b$ [latex](1 ≤ a, b ≤ 10^9)[/latex].

Выходные данные

Количество цифр $6$ в последовательных натуральных числах от $a$ до $b$.

Тесты

Ввод Вывод
1 5 256 46
2 56 110 16
3 27357 43577 5852
4 368325775 56 296285528
5 584937543 984938576 420000314

Код

Решение

Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.

Доказательство проведем по математической индукции.

  1. Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
  2. Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
  3. Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$

Разберёмся, как их нужно комбинировать. Для этого в цикле пройдёмся по каждой из цифр числа и полученные результаты просуммируем. В ответ мы выдадим разность количества шестерок без внешней границы.

Ссылки

Related Images: