Назовём ряд из двух цифр подходящим, если выполняется любое из двух условий:
1) сумма цифр чётна и вторая цифра больше первой;
2) сумма цифр нечётна и вторая цифра меньше первой.
Назовём многозначное число подходящим, если любые две соседние цифры в его записи образуют подходящий ряд.
Примеры подходящих чисел: 26, 63, 30, 2630, 26308.
Пример неподходящего числа: 2638. Это число нельзя считать подходящим, так как соседние
Сколько существует подходящих 12-значных 9-ричных чисел?
Рассмотрим какие числа могут получаться при составлении по условиям.
Рассмотрим двузначные числа.
Первой цифрой не может быть ноль, возьмем
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если первая
Если рассматривать трехзначные числа, то между второй и третьей цифрами к приведенным вариантам добавляется вариант
Таким образом, в 12-значном 9-ричном числе первую цифру можно выбрать
Всего 8 · 411 = 33554432 подходящих 12-значных 9-ричных чисел.
Ответ: 33554432.
Приведём решение на языке Python.
def f(n):
s = str(n)
if len(s) == 12:
return 1
podr = []
for i in range(9):
if (int(s[-1]) + i)%2 == 0 and i > int(s[-1]):
podr.append(int(s+str(i)))
if (int(s[-1]) + i)%2 != 0 and i < int(s[-1]):
podr.append(int(s + str(i)))
return sum(f(i) for i in podr)
print(sum(f(i) for i in range(1,9)))
Приведём решение Егора Чернецова на языке Python.
dp = [int(0 < d < 9) for d in range(9)]
for _ in range(11):
dp = [sum(dp[d] * (n > d if (d+n) % 2 == 0 else n < d) for d in range(9)) for n in range(9)]
print(sum(dp))
Приведём решение Юрия Красильникова на языке Python.
import functools
@functools.lru_cache(1000)
def kp(d,l):
if l==2: return len(dic[d])
return sum(kp(x,l-1) for x in dic[d])
dic={d:[x for x in range(9) if ((d+x)%2==0 and x > d) or ((d+x)%2==1 and x < d)] for d in range(9)}
print(sum(kp(x,12) for x in range(1,9)))
Приведём решение Сергея Донец на PascalABC.NET:
[cache]
function rec(pos, prev: integer): double :=
if ((pos = 13)) then 1.0 else
(0..8)
.Where(curr -> (pos = 1)or( (prev + curr) mod 2 = 0)and(curr > prev)or( (prev + curr) mod 2 = 1)and(curr < prev)and( (pos > 1)or(curr > 0) )
).Sum(curr -> rec((pos + 1), curr));
begin
Println( (1..8).Sum(start -> rec(2, start)) ); // 33554432
end.