Задача 5542. Источник: Поляков. Задание КИМ 23
(М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 2
- Умножь на 3
- Умножь на 4
Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений содержит ровно 5 чисел с суммой цифр 14.
Решение
Более компактный код на Python с передачей в рекурсивную функцию списка из вычисленных значений программы и возвратом количества программ.
Python
def r(a):
if a[-1] > 600:
return 0
if a[-1] == 600:
k = 0
for i in a:
s = 0
while i > 0:
s += i % 10
i //= 10
if s == 14:
k += 1
if k == 5:
return 1
return 0
return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])
print(r([1]))
С использованием итераторов, возможен анализ пути в одну строку, но любой подобный код работает от 30% дольше. Наилучшие результаты по времени дают следующие варианты:
def r(a):
if a[-1] > 600:
return 0
if a[-1] == 600:
if len([x for x in map(lambda n: sum([int(c) for c in str(n)]), a) if x == 14]) == 5:
return 1
return 0
return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])
print(r([1]))
или
def r(a):
if a[-1] > 600:
return 0
if a[-1] == 600:
if list(map(lambda n: sum([ord(c) - 48 for c in str(n)]), a)).count(14) == 5:
return 1
return 0
return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])
print(r([1]))
Наиболее универсальное, быстрое и экономичное по используемой памяти решение, которое можно реализовать на любом языке программирования, основано на использовании глобального массива или списка с передачей в рекурсивную функцию индекса последнего используемого элемента. Исходя из минимальной операции, в этой задаче будет достаточно массива из 301 элемента.
Python
def r(n=0):
if a[n] > 600:
return 0
if a[n] == 600:
k = 0
for i in range(n + 1):
z = a[i]
s = 0
while z > 0:
s += z % 10
z //= 10
if s == 14:
k += 1
if k == 5:
return 1
return 0
a[n + 1] = a[n] + 2
k = r(n + 1)
a[n + 1] = a[n] * 3
k += r(n + 1)
a[n + 1] = a[n] * 4
k += r(n + 1)
return k
a = [1] * 301
print(r())
PascalABC
var
a: Array [1..301] of Integer;
function r(n: Integer := 1): Integer;
var
k, s, z: Integer;
begin
Result := 0;
if a[n] > 600 then
Exit;
if a[n] = 600 then
begin
k := 0;
for var i := 1 to n do
begin
z := a[i];
s := 0;
while z > 0 do
begin
s := s + z mod 10;
z := z div 10;
end;
if s = 14 then
k := k + 1;
end;
if k = 5 then
Result := 1;
end
else
begin
a[n + 1] := a[n] + 2;
Result := Result + r(n + 1);
a[n + 1] := a[n] * 3;
Result := Result + r(n + 1);
a[n + 1] := a[n] * 4;
Result := Result + r(n + 1);
end;
end;
begin
a[1] := 1;
Writeln(r());
end.
C++
#include <iostream>
using namespace std;
int a[301];
int r(int n = 0)
{
if (a[n] > 600)
return 0;
if (a[n] == 600)
{
int k = 0;
for (int i = 0; i <= n; i++)
{
int z = a[i], s = 0;
while (z > 0)
{
s += z % 10;
z /= 10;
}
if (s == 14)
k++;
}
if (k == 5)
return 1;
return 0;
}
a[n + 1] = a[n] + 2;
int k = r(n + 1);
a[n + 1] = a[n] * 3;
k += r(n + 1);
a[n + 1] = a[n] * 4;
k += r(n + 1);
return k;
}
int main()
{
a[0] = 1;
cout << r() << endl;
}
Ответ
6120