Задача 5849. Источник: Поляков. Задание КИМ 23
(М. Ишимов) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
- Вычти 2
- Вычти минимальную ненулевую цифру числа
- Вычти остаток от деления на 4
Выполняя первую из них, исполнитель уменьшает значение на экране на 2, выполняя вторую – уменьшает на минимальную ненулевую цифру числа, выполняя третью – уменьшает на остаток от деления числа на 4. Программа для исполнителя – это последовательность команд, каждая из которых уменьшает число. Сколько существует программ, для которых при исходном числе 96 результатом является число 60, и при этом траектория вычислений содержит число 64? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABC при исходном числе 38 траектория будет состоять из чисел 36, 33, 32.
Решение
Напишем рекурсивную функцию перебора вариантов, принимающую два значения: исходное число s и конечное число e, а возвращающую количество траекторий. Стоит учитывать, что третья команда не должна использоваться, если остаток от деления равен нулю, т.к., в противном случае, количество траекторий бесконечно.
Python
def r(s, e):
if s < e:
return 0
if s == e:
return 1
m = 10
z = s
while z > 0:
if 0 < z % 10 < m:
m = z % 10
z //= 10
k = r(s - 2, e) + r(s - m, e)
if s % 4 != 0:
k += r(s - s % 4, e)
return k
print(r(96, 64) * r(64, 60))
PascalABC
function r(s: Integer; e: Integer): Integer;
var
m, z: Integer;
begin
if s < e then
Result := 0
else if s = e then
Result := 1
else
begin
m := 10;
z := s;
while z > 0 do
begin
if (z mod 10 > 0) and (z mod 10 < m) then
m := z mod 10;
z := z div 10;
end;
Result := r(s - 2, e) + r(s - m, e);
if s mod 4 <> 0 then
Result := Result + r(s - s mod 4, e);
end;
end;
begin
Writeln(r(96, 64) * r(64, 60));
end.
C++
#include <iostream>
using namespace std;
int r(int s, int e)
{
if (s < e)
return 0;
if (s == e)
return 1;
int m = 10, z = s;
while (z > 0)
{
if (z % 10 > 0 && z % 10 < m)
m = z % 10;
z /= 10;
}
int k = r(s - 2, e) + r(s - m, e);
if (s % 4 != 0)
k += r(s - s % 4, e);
return k;
}
int main()
{
cout << r(96, 64) * r(64, 60) << endl;
}
Ответ
37104