Задание 16. Информатика. ЕГЭ. Поляков-7251
- Просмотры: 191
- Изменено: 24 ноября 2024
*Обозначим через \(a \, \% \, b\) остаток от деления натурального числа \(a\) на натуральное число \(b\), а через \(a \, // \, b\) – целую часть от деления \(a\) на \(b\). Алгоритм вычисления значения функции \(F(n)\), где \(n\) – натуральное число, задан следующими соотношениями:
\(F(n) = 1\), если \(n = 0\),
\(F(n) = F(n \, // \, 100) \cdot (n \, \% \, 10)\), если \(n > 0\) и \(n\) нечётно;
\(F(n) = F(n \, // \, 100)\), если \(n > 0\) и \(n\) чётно.
Определите количество значений \(n\), таких что \(10^9 \leqslant n \leqslant 6 \cdot 10^9\), для которых \(F(n) = 21\).
Решение:
Реализация функции на Python
def F(n):
if n == 0:
return 1
elif n % 2:
return F(n // 100) * (n % 10)
return F(n // 100)
Целочисленное деление на \(100\) отбрасывает две последние цифры числа. Остаток от деления на \(10\) — это последняя цифра числа. В указанном в задаче диапазоне чисел используются \(10\) цифр для их записи. Таким образом, в формировании ответа участвуют только цифры, стоящие на чётных позициях. На нечётных могут стоять любые цифры от \(0\) до \(9\), кроме первой позиции. Здесь могут по условию задачи находиться только цифры от \(1\) до \(5\). (Число \(6~000~000~000\) не даст в ответ \(21\), поэтому мы его не рассматриваем.) Т.о., мы имеет \(5 \cdot 10^4\) различных вариантов для цифр, расположенных на нечётных позициях. На чётных, теперь, должны располагаться одна цифра \(3\), одна цифра \(7\) и на оставшихся трёх позициях могут быть только чётные цифры \(0, \, 2, \, 4, \, 6, \, 8\) или цифра \(1\). Пусть \(abc\) — это набор наших цифр на чётных позициях из \(6\) разрешённых. Всего получаем \(216\) разных вариантов. Теперь добавить цифру \(3\) мы можем четырьмя разными способами \(3abc\), \(a3bc\), \(ab3c\) и \(abc3\). В каждый такой набор, аналогично, мы можем \(5\)-ю различными способами добавить \(7\). Т.о., имеем \(4 \cdot 5 \cdot 216\) вариантов размещения цифр на чётных позициях. Всего, значит, будет \(4 \cdot 5 \cdot 216 \cdot 5 \cdot 10^4\) различных чисел из указанного диапазона, при котором в ответе получим \(21\).
Ответ: \(216000000\)