Задача
Сколько раз будет использована цифра $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 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 |
#include <iostream> using namespace std; int count_six(int input){ int rez = 0, mem = 1, length = 0, exp_10 = 1; short num; while(input > 0){ num = input % 10;//узнаём последний знак в числе input /= 10;//убираем последний разряд из числа if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1 else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов mem += num * exp_10; //запоминаем пройденное число length++; //отмечаем пройденный разряд } return rez; } int main() { int a, b; cin >> a >> b; if (a > b) swap(a, b); cout << count_six(b) - count_six(a - 1); return 0; } |
Решение
Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.
Доказательство проведем по математической индукции.
- Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
- Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
- Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$
Разберёмся, как их нужно комбинировать. Для этого в цикле пройдёмся по каждой из цифр числа и полученные результаты просуммируем. В ответ мы выдадим разность количества шестерок без внешней границы.
Ссылки
Related Images:
