Задача
Напишите программу, которая определяет количество чисел от $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.
Теперь сведем наше число к числу без восьмерок в записи. Для этого достаточно заменить в десятичной записи нашего числа все цифры стоящие справа от самой левой восьмерки на девятки, а саму восьмерку на семерку, так как все числа больше этого и меньше заданного содержат восьмерки.
Будем хранить наше число как массив его цифр (см. комментарии в коде).
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> using namespace std; #define ll unsigned long long int main() { ll n; cin >> n; int cnt = 0; // Считаем количество цифр while (x1) x1 /= 10, cnt++; int d[cnt], i = 1; ll x1 = n; // Заполняем массив цифр while (x1) d[cnt - i++] = x1 % 10, x1 /= 10; // Заменяем цифры после 8 на 799999... bool f = false; for (int i = 0; i < cnt; i++) if (f) d[i] = 9; else if (d[i] == 8) d[i] = 7, f = true; // Считаем степени девятки ll pow9[19]; pow9[0] = 1; for (int i = 1; i <= 18; i++) pow9[i] = pow9[i - 1] * 9; // Считаем ответ ll res = 0; for (int i = cnt - 1; i >= 0; i--) res += pow9[cnt - i - 1] * (d[i] - (d[i] >= 8)); cout << res << endl; } |
Ссылки
Задача на E-Olymp
Код на IdeOne