e-olymp 8688. Количество чисел без 8

Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные Вывод программы
10 9
25833798135522720 4918510377816614
88888888888888 20334926626631

Решение

Сначала решим нашу задачу для чисел, которые изначально не содержат цифры $8$ в записи. Для этого представим ответ на задачу как сумму ответов для чисел $10^k$, умноженных на соответствующую цифру разряда в исходном числе. Единственное что нужно сделать — если цифра разряда $a$ больше или равна $8$, то нужно умножать не на $a$, а на $a — 1$, так как мы не считаем числа с восьмерками. Ответы для степеней десятки будем хранить в массиве, нетрудно посчитать что $f(10^k) = 9^k$, так как мы можем взять на каждое место любую цифру кроме восьмерки, а их всего 10.
Теперь сведем наше число к числу без восьмерок в записи. Для этого достаточно заменить в десятичной записи нашего числа все цифры стоящие справа от самой левой восьмерки на девятки, а саму восьмерку на семерку, так как все числа больше этого и меньше заданного содержат восьмерки.
Будем хранить наше число как массив его цифр (см. комментарии в коде).

Код

Ссылки

Задача на E-Olymp
Код на IdeOne

Добавить комментарий