23 - Динамическое программирование

Источники:

сайт Полякова (https://kpolyakov.spb.ru/)

демонстрационная версия станции КЕГЭ (https://kompege.ru/)

1) (№4040) Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 2 и вычти 3

Сколько различных результатов можно получить из исходного числа 3 после выполнения программы, содержащей ровно 12 команд?

Решение

Вариант 1

def f(n,h):

global s

if h==12:

if s.find(':'+str(n)+':')==-1:

s+=str(n)+':'

else:

f(n+1,h+1)

f(n*2-3,h+1)

s=':'

f(3,0)

print(s.count(':')-1)

Вариант 2

def f(n,h):

global s

if h==12: s.add(n)

else:

f(n+1,h+1)

f(n*2-3,h+1)

s=set()

f(3,0)

print(len(s))

Ответ: 377

2) (№4039) Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 3

2. Умножь на 2 и прибавь 1

Сколько различных результатов можно получить из исходного числа 2 после выполнения программы, содержащей ровно 13 команд?

Решение

Вариант 1

def f(n,h):

global s

if h==13:

if s.find(':'+str(n)+':')==-1:

s+=str(n)+':'

else:

f(n+3,h+1)

f(n*2+1,h+1)

s=':'

f(2,0)

print(s.count(':')-1)

Вариант 2

def f(n,h):

global s

if h==13: s.add(n)

else:

f(n+3,h+1)

f(n*2+1,h+1)

s=set()

f(2,0)

print(len(s))

Ответ: 973

3) (№3747) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Прибавь 3

Сколько существует программ, которые преобразуют исходное число 5 в число 18, и при этом траектория вычислений содержит число 11 и не содержит чисел 10 и 15?

Решение

a,b,c=5,11,18

d1,d2=10,15

m=[0]*(max(a,b,c)+1)

m[a]=1

for k in range(2):

for i in range(a,b):

m[i+1]+=m[i]

if i+2<=b: m[i+2]+=m[i]

if i+3<=b: m[i+3]+=m[i]

m[d1],m[d2]=0,0

a,b=b,c

print(m[b])

Ответ: 176

4) (№3746) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Сколько существует программ, которые преобразуют исходное число 3 в число 21, и при этом траектория вычислений содержит число 8 и не содержит числа 12?

Решение

a,b,c=3,8,21

d1=12

m=[0]*(max(a,b,c)+1)

m[a]=1

for k in range(2):

for i in range(a,b):

m[i+1]+=m[i]

if i+3<=b: m[i+3]+=m[i]

if i*2<=b: m[i*2]+=m[i]

m[d1]=0

a,b=b,c

print(m[b])

Ответ: 228

5) (№3719 А.Комков) Исполнитель Нолик преобразует число, записанное на экране в четверичной системе счисления. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить 3

3. Добавить справа 0

Первая команда увеличивает число на 2. Вторая команда увеличивает число на 3. Третья команда приписывает к записи числа справа 0, например, для числа 123 результатом работы данной команды будет являться число 1230.

Сколько существует программ, которые число 1, записанное в четверичной системе счисления, преобразуют в четверичную запись 100?

Решение

a,b=1,16

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

if i+2<=b:m[i+2]+=m[i]

if i+3<=b: m[i+3]+=m[i]

if i*4<=b: m[i*4]+=m[i]

print(m[b])

Ответ: 43

6) (№3718 А.Комков) Исполнитель Нолик преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 2

2. Обнулить младший разряд

Первая команда уменьшает число на 2. Вторая команда обнуляет ненулевой младший разряд троичной записи числа. (Например, при выполнении этой команды число 21 преобразуется в число 20. Если в младшем разряде находится 0, то данная команда не выполняется).

Сколько существует программ, которые троичное число 212, преобразуют в троичное число 10?

Решение

a,b=2*3**2+1*3**1+2*3**0,3

m=[0]*(max(a,b)+1)

m[a]=1

for i in range(a,b,-1):

if i-2>=b:m[i-2]+=m[i]

if i-i%3>=b: m[i-i%3]+=m[i]

print(m[b])

Ответ: 86

7) (№3717 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 1

2. Обнулить

Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется.

Сколько существует программ, которые исходное двоичное число 1000000 преобразуют в двоичное число 1000?

Решение

Вариант 1

z=[2**6,2**5,2**4,2**3]

zi=0

a=2**6

b=2**3

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if i!=z[zi]: m[z[zi]]+=m[i]

else: zi+=1

print(m[b])

Вариант 2

a,b=2**6,2**3

m=[0]*(max(a,b)+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

c=bin(i)[2:]

if str(c).count('1')>1: m[int('1'+'0'*(len(c)-1),2)]+=m[i]

print(m[b])

Ответ: 4096

8) (№3716 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 1

2. Обнулить

Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется.

Сколько существует программ, которые исходное двоичное число 10001 преобразуют в двоичное число 1?

Решение

Вариант 1

z=[2**4,2**3,2**2,2,1]

zi=0

a=2**4+1

b=1

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if i!=z[zi]: m[z[zi]]+=m[i]

else: zi+=1

print(m[b])

Вариант 2

a,b=2**4+1,1

m=[0]*(max(a,b)+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

c=bin(i)[2:]

if str(c).count('1')>1: m[int('1'+'0'*(len(c)-1),2)]+=m[i]

print(m[b])

Вариант 3

def b2(x):

return 2**(len(bin(x))-3)

a=int('10001',2)

b=1

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if bin(i).count('1')>1:m[b2(i)]+=m[i]

print(m[b])

Ответ: 128

9) (№3714 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Добавить слева 1

Первая команда увеличивает число на 1. Вторая команда приписывает к двоичному числу слева 1, например, для числа 10 результатом работы данной команды будет являться число 110.

Сколько существует программ, которые исходное двоичное число 1 преобразуют в двоичное число 11111?

Решение

Вариант 1

z=[2,4,8,16,32]

zi=0

a=1

b=31

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if z[zi]==i:zi+=1

if z[zi]+i<=b:m[z[zi]+i]+=m[i]

print(m[b])

Вариант 2

a,b=1,int('11111',2)

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if int('1'+bin(i)[2:],2)<=b:m[int('1'+bin(i)[2:],2)]+=m[i]

print(m[b])

Ответ: 82

10) (№3713 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Добавить слева 1

Первая команда увеличивает число на 1. Вторая команда приписывает к двоичному числу слева 1, например, для числа 10 результатом работы данной команды будет являться число 110.

Сколько существует программ, которые исходное двоичное число 100 преобразуют в двоичное число 110001?

Решение

Вариант 1

z=[8,16,32,64]

zi=0

a=4

b=2**5+2**4+1

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if z[zi]==i:zi+=1

if z[zi]+i<=b:m[z[zi]+i]+=m[i]

print(m[b])

Вариант 2

a,b=int('100',2),int('110001',2)

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if int('1'+bin(i)[2:],2)<=b:m[int('1'+bin(i)[2:],2)]+=m[i]

print(m[b])

Ответ: 33

11) (№3712 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 1

2. Убрать последнюю цифру справа

Первая команда уменьшает число на 1. Вторая команда убирает последнюю справа цифру, например, для числа 110 результатом работы данной команды будет являться число 11.

Сколько существует программ, которые исходное двоичное число 110111 преобразуют в двоичное число 110?

Решение

a,b=int('110111',2),int('110',2)

m=[0]*(max(a,b)+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if i//2>=b: m[i//2]+=m[i]

print(m[b])

Ответ: 343

12) (№3710 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Добавить справа 0

3. Добавить справа 1

Первая команда увеличивает число на 1. При выполнении второй команды, исполнитель справа к числу приписывает 0, а при выполнении третьей команды справа к числу приписывает 1. (например, для числа 10 результатом работы данных команд будут являться числа 100 и 101 соответственно).

Сколько существует программ, которые исходное двоичное число 101 преобразуют в двоичное число 101110?

Решение

a,b=int('101',2),int('101110',2)

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i*2<=b:m[i*2]+=m[i]

if i*2+1<=b:m[i*2+1]+=m[i]

print(m[b])

Ответ: 254

13) (№3613 Е.Джобс) Исполнитель Простачок преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить 3

3. Умножить на 2

Первая команда увеличивает число на 2, вторая – на 3, третья – увеличивает число вдвое. Сколько различных чисел может быть получено из числа 10 всеми возможными алгоритмами длиной 5 команд?

Решение

Вариант 1 (t = 0.015 сек.)

def f(n,h):

global s

if h==5: s.add(n)

else: f(n+2,h+1); f(n+3,h+1); f(n*2,h+1)

s=set()

f(10,0)

print(len(s))

Вариант 2 (t = 0.009 сек.)

def f(n,h):

if h==5 and not(n in m): m.append(n); return 1

if h==5: return 0

return f(n+2,h+1)+f(n+3,h+1)+f(n*2,h+1)

m=[]

print(f(10,0))

Вариант 3 (t = 0.009 сек.)

m1=[0]*1000

m1[10]=1

a=b=10

for p in range(5):

m2=[0]*1000

for i in range(a,b+1):

if m1[i]==1: m2[i+2]=1; m2[i+3]=1; m2[i*2]=1;b=i*2

a=a+2

m1=m2[:]

print(sum(m1))

Ответ: 83

14) (№3612 Е.Джобс) Исполнитель ЛенивыйСчетовод преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить 3

3. Дописать к числу справа 1

Первая команда увеличивает число на 2, вторая – на 3, третья – приписывает к текущему значению цифру 1 (например, для 10 результатом выполнения данной команды будет 101). Сколько существует таких программ, которые исходное число 3 преобразуют в число 25, при этом траектория вычислений содержит число 12?

Решение

a,b,c=3,12,25

m=[0]*(c+1)

m[a]=1

for i in range(2):

for i in range(a,b):

if i+2<=b: m[i+2]+=m[i]

if i+3<=b: m[i+3]+=m[i]

if i*10+1<=b: m[i*10+1]+=m[i]

a,b=b,c

print(m[b])

Ответ: 80

15) (№3611 Е.Джобс) Исполнитель Простачок преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить предыдущее

3. Прибавить следующее

Первая команда увеличивает число на 2, вторая – на предыдущее (например, число 5 будет преобразовано по правилу 5 + 4), третья – на следующее (аналогично, 5 по правилу 5 + 6 = 11). Сколько существует таких программ, которые исходное число 7 преобразуют в число 63, и при этом траектория вычислений не содержит число 43?

Решение

a,b=7,63

d=43

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

if i+2<=b: m[i+2]+=m[i]

if i*2+1<=b: m[i*2+1]+=m[i]

if i*2-1<=b: m[i*2-1]+=m[i]

m[d]=0

print(m[b])

Ответ: 116

16) (№3610 Е.Джобс) Исполнитель Умножитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Умножить на 2

2. Умножить на 3

Первая команда увеличивает число на экране в 2 раза, вторая – увеличивает значение в 3 раза. Сколько существует программ, для которых при исходном числе 8 результатом является число 3456, и при этом траектория вычислений содержит число 96.

Решение

a,b,c=8,96,3456

m=[0]*(c+1)

m[a]=1

for i in range(2):

for i in range(a,b):

if i*2<=b: m[i*2]+=m[i]

if i*3<=b: m[i*3]+=m[i]

a,b=b,c

print(m[b])

Ответ: 18

17) (№3608 Е.Джобс) Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 2

2. Сделать простое

Первая команда увеличивает число на экране на 2, вторая – получает ближайшее бóльшее простое число. Сколько существует программ, для которых при исходном числе 2 результатом является число 45 и при этом траектория вычислений содержит число 14 и не содержит числа 33?

Решение

def pint(n):

if n % 2 == 0:

return n == 2

d = 3

while d * d <= n and n % d != 0:

d += 2

return d * d > n

a,b,c=2,14,45

d=33

m=[0]*(c+1)

m[a]=1

for k in range(2):

for i in range(a,b):

if i+2<=b:m[i+2]+=m[i]

pr=i

if pint(pr): pr+=1

while not(pint(pr)): pr+=1

if pr<=b: m[pr]+=m[i]

m[d]=0

a,b=b,c

print(m[b])

Ответ: 881

18) (№3606 Е.Джобс) Исполнитель Остаточек преобразует числа и имеет следующие команды:

1. Прибавить 1

2. Умножить на 2

3. Прибавить остаток от деления на 4

Первая команда увеличивает число на единицу, вторая – увеличивает вдвое, третья команда добавляет к числу значение остатка от деления этого числа на 4. Определите, сколько существует чисел, из которых Остаточек может получить число 80 с помощью программы длиной не более 5 команд.

Решение

def f(n,h):

global s,i

if h<=5:

if n==80:s.add(i)

f(n+1,h+1)

f(n*2,h+1)

f(n+n%4,h+1)

s=set()

for i in range(80+1):

f(i,0)

print(len(s))

Ответ: 34

19) (№3452 А.Н.Носкин) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить 4

3. Прибавить 5

Определите число, для получения которого из числа 31 существует 1001 программа.

Решение

m=[0]*1000

m[31]=1

i=31

while m[i]!=1001:

m[i+2]+=m[i]

m[i+4]+=m[i]

m[i+5]+=m[i]

i+=1

print(i)

Ответ: 56

20) (№3451 А.Н.Носкин) У исполнителя Калькулятор есть две команды, которым присвоены номера:

1. Прибавить 2

2. Прибавить 5

Определите число, для получения которого из числа 5 существует 34 программы.

Решение

m=[0]*1000

m[5]=1

i=5

while m[i]!=34:

m[i+2]+=m[i]

m[i+5]+=m[i]

i+=1

print(i)

Ответ: 27

21) (№3450 С.С.Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Определите число, для получения которого из числа 1 существует 175 программ.

Решение

m=[0]*1000

i=1

m[i]=1

while m[i]!=175:

m[i+1]+=m[i]

m[i+5]+=m[i]

m[i*3]+=m[i]

i+=1

print(i)

Ответ: 19

22) (№3449 С.С.Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Сколько разных чисел на отрезке [1000, 1024] может быть получено из числа 1 с помощью программ, состоящих из 8 команд?

Решение

def f(n,h):

global s

if h==8:

if 1000<=n<=1024:s.add(n)

else:

f(n+1,h+1)

f(n+5,h+1)

f(n*3,h+1)

s=set()

f(1,0)

print(len(s))

Ответ: 1

23) (№3448 С.С.Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Сколько разных чисел на отрезке [34, 59] может быть получено из числа 1 с помощью программ, состоящих из 6 команд?

Решение

def f(n,h):

global s

if h==6:

if 34<=n<=59: s.add(n)

else:

f(n+1,h+1)

f(n+2,h+1)

f(n*2,h+1)

s=set()

f(1,0)

print(len(s))

Ответ: 11

24) (№3447 С.С.Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Сколько разных чисел может быть получено из числа 1 с помощью программ, состоящих из 7 команд?

Решение

def f(n,h):

global s

if h==7:s.add(n)

else:

f(n+1,h+1)

f(n+5,h+1)

f(n*3,h+1)

s=set()

f(1,0)

print(len(s))

Ответ: 393

25) (№3106) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

Сколько есть программ, которые число 12 преобразуют в число 36?

Решение

a,b=12,36

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i//10%10<9:

if i+10<=b: m[i+10]+=m[i]

print(m[b])

Ответ: 31

26) (№3105) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ, которые число 25 преобразуют в число 51?

Решение

Вариант 1

a,b=25,51

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i%100!=99:

if i%10<9:

if i+11<=b: m[i+11]+=m[i]

else:

if i+10<=b: m[i+10]+=m[i]

print(m[b])

Вариант 2 (работает с любым диапазоном a и b)

a,b=25,51

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

i1=str(i)

for a in '876543210':

i1=i1.replace(a,str(int(a)+1))

if int(i1)<=b:m[int(i1)]+=m[i]

print(m[b])

Ответ: 33

27) (№3097) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 1,5

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число

в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 2 преобразуют в число 22?

Решение

a,b=2,22

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i%2==0 and i*1.5<=b: m[int(i*1.5)]+=m[i]

print(m[b])

Ответ: 44

28) (№3095) У исполнителя Калькулятор четыре команды, которым присвоены номера:

1. прибавь 1

2. сделай чётное

3. сделай нечётное

4. умножь на 10

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15?

Решение

a,b=1,15

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i*2<=b: m[i*2]+=m[i]

if i*2+1<=b: m[i*2+1]+=m[i]

if i*10<=b: m[i*10]+=m[i]

print(m[b])

Ответ: 84

29) (№3089) У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 2

3. прибавь предыдущее

Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 9?

Решение

a,b=2,9

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i+2<=b: m[i+2]+=m[i]

if i*2-1<=b: m[i*2-1]+=m[i]

print(m[b])

Ответ: 57

30) (№2767 А.Е.Гребенкин) Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Вычесть 1

2. Вычесть 3

3. Взять остаток от деления на 4

Команда 3 выполняется только для чисел, больших, чем 4. Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

Решение

a,b=22,2

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if i-3>=b: m[i-3]+=m[i]

if i%4>=b and i>4: m[i%4]+=m[i]

print(m[b])

Ответ: 1873

31) (№2766 А.Е.Гребенкин) Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Вычесть 1

2. Вычесть 3

3. Разделить нацело на 3

При выполнении команды 3 выполняется деление нацело (остаток отбрасывается). Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

Решение

a,b=22,2

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

if i-3>=b: m[i-3]+=m[i]

if i//3>=b: m[i//3]+=m[i]

print(m[b])

Ответ: 2196

32) (№2504 Т.В.Белова) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

3. Возвести в квадрат

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 19?

Решение

a,b=2,19

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i+3<=b: m[i+3]+=m[i]

if i*i<=b: m[i*i]+=m[i]

print(m[b])

Ответ: 627

33) (Е.Джобс - вариант 11022021) Исполнитель Кампухтер преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 3

2. Умножить на 3

Сколько положительных четных чисел, меньших 100, может получить исполнитель из числа 3?

Решение

a,b=3,100

m=[0]*(b+1)

m[a]=1

s=0

for i in range(a,b):

if m[i]==1:

if i%2==0:s+=1

if i+3<=b: m[i+3]=1

if i*3<=b: m[i*3]=1

print(s)

Ответ: 16

34) (№3444 С.С.Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Сколько существует программ минимальной длины, в результате выполнения которых при исходном числе 1 результатом является число 28?

Решение

def f(x,n):

global mi,kmi

if x==28:

if n< mi:

mi=n

kmi=1

elif mi==n: kmi+=1

elif x<28:

f(x*2,n+1)

f(x+2,n+1)

f(x+1,n+1)

mi=1000

kmi=0

f(1,1)

print(kmi)

Ответ: 3

35) (№4103 Е.Джобс) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 3

2. Умножь на 3

Сколько различных чётных чисел, меньших 100, может получить Калькулятор из исходного числа 3?

Решение

a,b=3,100

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

if i+3<=b:m[i+3]+=m[i]

if i*3<=b:m[i*3]+=m[i]

k=0

for i in range(2,b,2):

if m[i]>0:k+=1

print(k)

Ответ: 16

36) (№5012 М.Фирсов) Исполнитель Счеты преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 4

2. Прибавь 7

3. Раздели нацело на 2

Первая команда увеличивает число на экране на 4, вторая увеличивает его на 7, третья делит на 2 нацело (остаток отбрасывается). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые состоят из 10 команд и при исходном числе 1 результатом является 1?

Решение

def f(x,h):

global k

if h==10:

if x==1:k+=1

else:

f(x+4,h+1)

f(x+7,h+1)

f(x//2,h+1)

k=0

f(1,0)

print(k)

Ответ: 917

37) (№2941 Апробация 19 февраля 2022 года, Москва ) Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 32, и при этом траектория вычислений содержит число 12 и не содержит числа 15?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение

a,b,c,d=2,12,32,15

m=[0]*(c+1)

m[a]=1

for h in range(2):

for i in range(a,b):

m[i+1]+=m[i]

if i*2<=b: m[i*2]+=m[i]

m[d]=0

a,b=b,c

print(m[c])

Ответ: 30

38) (№5074 А.Бычков) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 79, и при этом траектория вычислений содержит число 11 и не содержит число 23. Также программа не должна содержать двух команд «Прибавь 1» подряд.

Решение

a,b,c=3,11,79

d=23

m1,m2=[0]*(c+1),[0]*(c+1)

m2[a]=1

for k in range(2):

for i in range(a,b):

m1[i+1]+=m2[i]

if i+2<=b:m2[i+2]+=m1[i]+m2[i]

if i*2<=b:m2[i*2]+=m1[i]+m2[i]

m1[d]=m2[d]=0

a,b=b,c

print(m1[b]+m2[b])

Ответ: 812266767

39) (№ 4126 А.Богданов) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

Первая команда увеличивает число на 1, вторая – на 2. Сколько существует таких программ, которые исходное число 11 преобразуют в число 29, и при этом траектория вычислений содержит либо 17, либо 23, либо 17 и 23 одновременно?

Решение

a,b=11,29

d1,d2=17,23

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i+2<=b:m[i+2]+=m[i]

sp=m[b]

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i+2<=b:m[i+2]+=m[i]

m[d1],m[d2]=0,0

print(sp-m[b])

Ответ: 3861

40) (№2761) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, состоящих из 6 команд, для которых при исходном числе 1 результатом является число 20?

Решение

def f(n,h):

global k

if h==6:

if n==20:k+=1

else:

f(n+1,h+1)

f(n+2,h+1)

f(n*2,h+1)

k=0

f(1,0)

print(k)

Ответ: 36

41)(№2765) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Прибавить 3

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, состоящих из 7 команд, для которых при исходном числе 3 результатом является число 22?

Решение

def f(n,h):

global k

if h==7:

if n==22:k+=1

else:

f(n+1,h+1)

f(n+2,h+1)

f(n+3,h+1)

k=0

f(3,0)

print(k)

Ответ: 28

42)(№5937 Д.Статный) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

А. Прибавить 2.

Б. Прибавить 3.

С. Умножить на 2 и прибавить 1.

Первая команда увеличивает на 2, вторая – увеличивает на 3, третья – умножает на 2 и увеличивает на 1. Сколько существует таких программ, которые исходное число 1 преобразуют в число 55, и при этом траектория содержит не более 15-х чётных чисел.

Решение

def f(s,ch):

global k

if ch<=15:

if s==55: k+=1

elif s<55:

if s%2==0:ch+=1

f(s+2,ch)

f(s+3,ch)

f(s*2+1,ch)

k=0

f(1,0)

print(k)

Ответ: 4197234

43)(№5936 Д.Статный) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

А. Прибавить 2.

Б. Прибавить 3.

С. Умножить на 2 и прибавить 1.

Первая команда увеличивает на 2, вторая – увеличивает на 3, третья – умножает на 2 и увеличивает на 1. Сколько существует таких программ, которые исходное число 1 преобразуют в число 625, и при этом траектория содержит не более 4-х нечётных чисел.

Решение

def f(s,nch):

global k

if nch<=4:

if s==625:k+=1

elif s<625:

if s%2:nch+=1

f(s+2,nch)

f(s+3,nch)

f(s*2+1,nch)

k=0

f(1,1) # 1(один) - нечетное число и его надо учитывать

print(k)

Ответ: 110731

44)(№5837 Д.Статный) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

А. Прибавить младший разряд числа.

Б. Умножить на старший разряд числа.

С. Умножить на 2 и прибавить сумму цифр числа.

Первая команда увеличивает число на младший разряд числа, вторая – умножает на старший разряд числа, третья – умножает на 2 и прибавляет сумму цифр числа. Каждая команда изменяет число. Сколько существует таких программ, которые исходное число 10 преобразуют в число 4096?

Решение

a,b=10,4096

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

ik=i+int(str(i)[-1])

if ik<=b and ik!=i:m[ik]+=m[i]

ik=i*int(str(i)[0])

if ik<=b and ik!=i:m[ik]+=m[i]

ik=i*2+sum(map(int,str(i)))

if ik<=b and ik!=i:m[ik]+=m[i]

print(m[b])

Ответ: 49340685

45)(№5236) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 2

2. Умножь на 3

3. Умножь на 4

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 2 в число 400, и при этом траектория вычислений содержит более 50 различных чисел (без учёта начального и конечного)?

Решение

def f(s,n):

global k

if s==400:

if n-1>5: k+=1 # не учитываем конечьное число (400)

elif s<400:

n+=1

f(s+2,n)

f(s*3,n)

f(s*4,n)

k=0

f(2,0)

print(k)

Ответ: 6142

46)(№4500 А.Бычков) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 79, и при этом траектория вычислений содержит число 11 и не содержит число 23. Также программа не должна содержать двух команд «Прибавь 1» подряд.

Решение

a,b,c=3,11,79

d=23

m,m1=[0]*(c+1),[0]*(c+1)

m[a]=1

for p in range(2):

for i in range(a,b):

m1[i+1]+=m[i]

if i+2<=b: m[i+2]+=m[i]+m1[i]

if i*2<=b: m[i*2]+=m[i]+m1[i]

m[d]=0;m1[d]=0

a,b=b,c

print(m[b]+m1[b])

Ответ: 812266767

47)(№4498 М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Умножь на 5

2. Умножь на 3

3. Прибавь 45

Первая команда умножает число на экране на 5, вторая – умножает на 3, третья – увеличивает на 45. Сколько существует различных программ, которые преобразуют исходное число 1 в число 2970, и при этом траектория вычислений не более 4 команд «умножь на 5», не менее 2 команд «умножь на 3», и ровно 5 команд «прибавь 45»?

Решение

Решение 1

def f(s,k3,k5,k45):

global k

if s==2970:

if k3>=2 and k5<=4 and k45==5:k+=1

elif s<=2970:

f(s*3,k3+1,k5,k45)

f(s*5,k3,k5+1,k45)

f(s+45,k3,k5,k45+1)

k=0

f(1,0,0,0)

print(k)

Решение 2

def f(a,s):

global k

if a==2970:

d1=s.count('1')

d2=s.count('2')

d3=s.count('3')

if d1<=4 and d2>=2 and d3==5:

k+=1

elif a<2970:

f(a*5,s+'1')

f(a*3,s+'2')

f(a+45,s+'3')

k=0

f(1,'')

print(k)

Ответ: 74

48)(№3899 Джобс ) Исполнитель преобразует двузначные числа с помощью двух команд:

1. запиши сумму разрядов числа;

2. запиши произведение разрядов числа.

Выполняя первую из них, исполнитель складывает разряды числа и выводит соответствующее значение на экран. При выполнении второй команды находится произведение разрядов, которое выводится на экран.

Программой для исполнителя называется последовательность команд.

Например, программа 221 примененная к числу 93 выполнится следующим образом: 9*3 = 27, 2*7 = 14, 1+4 = 5

Сколько существует чисел, для которых существует программа, получающая в результате число 8?

Решение

def f(a,c):

global m

if a==8: m.add(c)

elif a>9 and not( c in m):

f(sum(map(int,str(a))),c)

sp=1

for i in str(a): sp*=int(i)

f(sp,c)

m=set()

for i in range(10,100): f(i,i)

print(len(m))

Ответ: 34

49)(№3780) Исполнитель Егорыч-2004 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь ближайшее простое число (большее самого числа)

2. Прибавь следующее число, являющиеся степенью двойки

3. Прибавь последнюю цифру, если она не равна нулю

Для примера рассмотрим команды для числа 15 :

1. Ближайшее простое число для него равно 17. Результатом выполнения этой командой будет 15+17=32.

2. Ближайшее число, являющиеся степенью двойки для него равно 16. Результатом выполнения этой командой будет 15+16=31.

3. Результатом выполнения этой командой будет 15+5=20.

Сколько существует программ, которые преобразуют исходное число 2 в число 3072, содержит число 1024 и не содержит чисел 3 и 14? В ответе выведите искомое количество программ.

Решение

def pr(x):

if x%2==0: return x==2

d=3

while x%d!=0 and d*d<=x:d+=2

return d*d>x

a,b,c=2,1024,3072

s2=[1]

while s2[-1]*2<=c*2:s2.append(s2[-1]*2) # c*2 для наличия в списке числа больше значения с

d1,d2=3,14

m=[0]*(c+1)

m[a]=1

i2=0

for p in range(2):

for i in range(a,b):

h=i+1

while not(pr(h)):h+=1

if i+h<=b: m[i+h]+=m[i]

while s2[i2]<=i:i2+=1

if i+s2[i2]<=b: m[i+s2[i2]]+=m[i]

pc=int(str(i)[-1])

if pc>0 and i+pc<=b: m[i+pc]+=m[i]

m[d1]=0;m[d2]=0

a,b=b,c

print(m[b])

Ответ: 21163425

50)(№3742 Джобс ) На экране есть два окна, в каждом из которых написано по числу. У исполнителя Сумматор две команды, которым присвоены номера:

1. запиши сумму чисел в первое окно

2. запиши сумму чисел во второе окно

Выполняя первую из них, Сумматор складывает числа в окнах и заменяет этой суммой число в первом окне, а выполняя вторую, складывает числа и заменяет этой суммой число во втором окне.

Сколько существует программ для Сумматора таких, что в результате его работы из пары чисел (1, 1) получится пара с суммой 88?

Решение

def f(s1,s2):

global k

if s1+s2==88: k+=1

elif s1+s2<88:

f(s1+s2,s2)

f(s1,s1+s2)

k=0

f(1,1)

print(k)

Ответ: 40

51)(№3374 Джобс ) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 2

2. Вычти 3

Первая команда увеличивает число на экране на 2, вторая уменьшает на 3. При выходе за диапазон чисел [-50; 50] исполнитель аварийно завершает свою работу.

Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 30 и при этом траектория вычислений не содержит одинаковых чисел?

Решение

def f (s,p):

global k

if s==30:

k+=1

elif -50<=s<=50:

p+=str(s)+':'

if not(':'+str(s+2)+':' in p):f(s+2,p)

if not(':'+str(s-3)+':' in p):f(s-3,p)

k=0

p=':'

f(1,p)

print(k)

Ответ: 851 (Время выполнений 178с.)

52)(№11483 PRO100_ЕГЭ ) Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Прибавить 1

B. Прибавить 3
C. Умножить на 3

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 31, при этом траектория вычислений содержит одновременно и число 9, и число 27?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 24, 25.

Решение

a,b,c,d=3,9,27,31

m=[0]*(d+1)

m[a]=1

for h in range(3):

for i in range(a,b):

m[i+1]+=m[i]

if i+3<=b: m[i+3]+=m[i]

if i*3<=b: m[i*3]+=m[i]

a,b,c=b,c,d

print(m[d])

Ответ: 12516

53)(№10723 PRO100_ЕГЭ ) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Прибавить 2
B. Возвести в квадрат
C. Возвести в куб

Программа для исполнителя – это последовательность команд.

Команда А прибавляет к числу 2. Например, из числа 68 получится число 68 + 2 = 70.
Команда B возводит число в квадрат. Например, из числа 9 получится число 92 = 81.
Команда C возводит число в куб. Например, из числа 4 получится число 43 = 64.

Сколько существует программ, для которых при исходном числе 10 результатом является число 1000?

Решение

a,b=10,1000

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

if i+2<=b: m[i+2]+=m[i]

if i**2<=b: m[i**2]+=m[i]

if i**3<=b: m[i**3]+=m[i]

print(m[b])

Ответ: 13

54)(№5836 Д.Статный) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть четыре команды, которым присвоены номера:

А. Прибавить ближайшее число, делящееся на 3.

Б. Прибавить ближайшее простое число, большее самого числа.

В. Прибавить ближайшее число, являющееся степенью 2, большее самого числа.

Г. Прибавить младший разряд числа, если он не равен 0.

Первая команда увеличивает число на ближайшее число, делящееся на 3; вторая – увеличивает на ближайшее простое число; третья – прибавляет ближайшее число, являющееся степенью 2; четвёртая – прибавляет младший разряд числа, не равный 0. Сколько существует таких программ, которые преобразуют исходное число 4 в 1228?

Решение

m2=[8]

for i in range(12): m2.append(m2[-1]*2)

m=[1]*2000;m[0]=m[1]=0

for i in range(2,int(2000**0.5)+1):

if m[i]:

for l in range(i*i,2000,i):m[l]=0

mp=[]

for i in range(2000):

if m[i]: mp.append(i)

a,b=4,1228

m=[0]*(b+1)

m[a],i2,ip=1,0,2

for i in range(a,b):

a3=i//3*3

if i-a3==2:a3+=3

if i+a3<=b:m[i+a3]+=m[i]

if m2[i2]==i: i2+=1;

if i+m2[i2]<=b:m[i+m2[i2]]+=m[i]

if mp[ip]<=i:ip+=1

if i+mp[ip]<=b:m[i+mp[ip]]+=m[i]

mr=i%10

if i+mr<=b and mr!=0:m[i+mr]+=m[i]

print(m[b])

Ответ: 17424908

55)(№6093 /dev/inf 02.2023) Исполнитель ТриКоманды преобразует число на экране.

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает число на 2, третья умножает его на 3. Программа для исполнителя ТриКоманды – это последовательность команд.

Сколько существует программ, состоящих не более чем из 3 команд, для которых при исходном числе 4 результатом является четное число?

Решение

def f(a,s):

global k

if len(s)<=3:

if a%2==0: k+=1

f(a+1,s+'1')

f(a+2,s+'2')

f(a*3,s+'3')

k=0

f(4,'')

print(k)

Ответ: 22

56)(№5838 Д.Статный) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

А. Прибавить 3.

Б. Прибавить 2.

С. Умножить на 2.

Первая команда увеличивает число на 3, вторая – на 2, третья – умножает на 2. Сколько существует таких программ, которые исходное число 1 преобразуют в число 50, и при этом точно известно, что каждая вторая команда – Б, а количество команд при выполнении программы нечётно?

Решение

def f(a,s):

global k

if a==50:

if len(s)%2!=0: k+=1

elif a<50:

f(a+2,s+'Б')

if len(s)%2==0:

f(a+3,s+'А')

f(a*2,s+'С')

k=0

f(1,'')

print(k)

Ответ: 1669

57)(№5640 М.Ишимов) Исполнитель преобразует число на экране.

У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Вычти 4

B. Вычти сумму цифр числа

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 36 результатом является число 2, и при этом траектория вычислений содержит число 14?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 33 траектория будет состоять из чисел 29, 18, 14.

Решение

Решение 1

a,b,c=36,14,2

m=[0]*(a+1)

m[a]=1

for i in range(2):

for i in range(a,b,-1):

if i-4>=b: m[i-4]+=m[i]

s=sum(map(int,str(i)))

if i-s>=b: m[i-s]+=m[i]

a,b=b,c

print(m[b])

Решение 2

def f(a,b):

global k

if a==b: k+=1

if a>b:

f(a-4,b)

s=sum(map(int,str(a)))

f(a-s,b)

k=0;f(36,14);p=k

k=0;f(14,2);p*=k

print(p)

Ответ: 7

58)(№4601 Основная волна 2022) Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Вычти 1

2. Найди целую часть от деления на 2

Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.

Решение

a,b,c=30,12,1

m=[0]*(a+1)

m[a]=1

for h in range(2):

for i in range(a,b,-1):

m[i-1]+=m[i]

if i//2>=b: m[i//2]+=m[i]

a,b=b,c

print(m[b])

Ответ: 376

59)(№5849 И.Ишимов) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Вычти 2
B. Вычти минимальную ненулевую цифру числа
C. Вычти остаток от деления на 4

Выполняя первую из них, исполнитель уменьшает значение на экране на 2, выполняя вторую – уменьшает на минимальную ненулевую цифру числа, выполняя третью – уменьшает на остаток от деления числа на 4. Программа для исполнителя – это последовательность команд, каждая из которых уменьшает число. Сколько существует программ, для которых при исходном числе 96 результатом является число 60, и при этом траектория вычислений содержит число 64? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABC при исходном числе 38 траектория будет состоять из чисел 36, 33, 32.

Решение

a,b,c=96,64,60

m=[0]*(a+1)

m[a]=1

for p in range(2):

for i in range(a,b,-1):

if i-2>=b: m[i-2]+=m[i]

a4=i%4

if a4>0 and i-a4>=b:m[i-a4]+=m[i]

amin=10

for r in str(i):

if r!='0': amin=min(amin,int(r))

if i-amin>=b:m[i-amin]+=m[i]

a,b=b,c

print(m[c])

Ответ: 37104

60)(№5788 М.Байрамгулов) Исполнитель перемещается на координатной плоскости. У исполнителя есть три команды, которым присвоены номера:

1. Увеличь x на 1
2. Умножь x на 2
3. Увеличь y на 3

Выполняя первую из них, исполнитель увеличивает координату x на 1, выполняя вторую – умножает на 2, выполняя третью – увеличивает координату y на 3. Программой для исполнителя называется последовательность команд. Сколько существует программ, при выполнении которых исполнитель из точки (1,0) переместится в точку (17, 27)?

Решение

def f(x,y):

global k

if x==17 and y==27: k+=1

elif x<17 or y<27:

if x<17:

f(x+1,y)

if x*2<=17:f(x*2,y)

if y+3<=27:f(x,y+3)

k=0

f(1,0)

print(k)

Ответ: 11973104

61)(№5786 М.Байрамгулов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1
2. Умножь на 2
3. Вычти 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – умножает на 2, выполняя третью – уменьшает на 3. Программой для исполнителя называется последовательность команд. Сколько существует программ длиной не более 7 команд, которые преобразуют число 1 в число 10?

Решение

def f(a,h):

global k

if h<=7 and a==10:k+=1

elif h<7:

f(a+1,h+1)

f(a*2,h+1)

f(a-3,h+1)

k=0

f(1,0)

print(k)

Ответ: 38

62)(№4166) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 2

3. Умножь на 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Определите длину самой короткой программы, которая преобразует число 1 в число 32718. Под длиной программы понимается количество команд, входящих в неё.

Решение

def f(x,h,s):

global minh,sm

if h<minh:

if x == 32718:

if minh>h: sm=s;minh=h

elif x<32718:

f(x*3,h+1,s+'3')

f(x*2,h+1,s+'2')

f(x+1,h+1,s+'1')

minh=20

f(1,0,'')

print(minh,sm)

Ответ: 17

63)(№12253) Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:

А. Прибавить 1

В. Прибавить 3

С. Возвести в квадрат

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 26, при этом траектория вычислений содержит число 20 и не содержит числа 16?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы СВА при исходном числе 4 траектория будет состоять из чисел 16, 19, 20.

Решение

a,b,c=3,20,26

d=16

m=[0]*(c+1)

m[a]=1

for p in [1,2]:

for i in range(a,b):

m[i+1]+=m[i]

if i+3<=b:m[i+3]+=m[i]

if i**2<=b:m[i**2]+=m[i]

m[d]=0

a,b=b,c

print(m[c])

Ответ: 936

64)(№678 Джобс 09.11.2020) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 3

3. Умножить на 4

Сколько существует программ, для которых при исходном числе 2 результатом является число 60 и при этом траектория вычислений содержит число 16 и не содержит число 21?

Решение

a,b,c=2,16,60

d=21

m=[0]*(c+1)

m[a]=1

for p in range(2):

for i in range(a,b):

m[i+1]+=m[i]

if i*3<=b: m[i*3]+=m[i]

if i*4<=b: m[i*4]+=m[i]

m[d]=0

a,b=b,c

print(m[c])

Ответ: 40

65)(№2762) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 2
3. Прибавить 3

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, состоящих из 7 команд, для которых при исходном числе 3 результатом является число 22?

Решение

def f(x,h):

global k

if h==7 and x==22: k+=1

elif h<7: f(x+1,h+1); f(x+2,h+1); f(x+3,h+1)

k=0

f(3,0)

print(k)

Ответ: 28

66)(№3103) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1
2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34 а 29 в 39 (так как младший разряд нельзя увеличить). Программа для Калькулятора – это последовательность команд. Сколько существует программ, которые число 26 преобразуют в число 49?

Решение

a,b=26,49

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i%10==9:h=10

else: h=11

if i+h<=b:m[i+h]+=m[i]

print(m[b])

Ответ: 22

67)(№2764) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2
3. Умножить на 3

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, состоящих из 8 команд, для которых при исходном числе 1 результатом является число 34?

Решение

def f(x,h):

global k

if h==8 and x==34: k+=1

elif h<8: f(x+1,h+1); f(x*2,h+1); f(x*3,h+1)

k=0

f(1,0)

print(k)

Ответ: 21

68)(№16387 ЕГКР 27.04.24 ) Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:

A. Прибавить 1
B. Прибавить 2
C. Умножить на 3

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 18, и при этом траектория вычислений содержит число 9 и не содержит числа 16?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория состоит из чисел 12, 14, 15.

Решение

Вариант 1

a,b,c=2,9,18

d=16

m=[0]*(c+1)

m[a]=1

for p in range(2):

for i in range(a,b):

m[i+1]+=m[i]

if i+2<=b:m[i+2]+=m[i]

if i*3<=b:m[i*3]+=m[i]

m[d]=0

a,b=b,c

print(m[b])

Вариант 2

def f(x,b):

if x==b: return 1

if x==16: return 0

if x<b:return f(x+1,b)+f(x+2,b)+f(x*3,b)

return 0

print(f(2,9)*f(9,18))

Ответ: 325

69)(№13302 М.Попков) Исполнитель преобразует двоичное число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Приписать справа двоичную запись остатка от деления на 5

Сколько существует программ, которые преобразуют исходное число 12 в число 1010001012 ?

Решение

Вариант 1 (t=0.01 c.)

a,b=1,325

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

p=int(bin(i)[2:]+bin(i%5)[2:],2)

if p<=b:m[p]+=m[i]

print(m[b])

Вариант 2 (t=12.42 c.)

def f(x,b):

if x==b: return 1

if x<b:

return f(x+1,b)+f(int(bin(x)[2:]+bin(x%5)[2:],2),b)

return 0

print(f(1,325))

Вариант 3 использование кэшаирования (t=0.12 c.)

from functools import *

@lru_cache()

def f(x,b):

if x==b: return 1

if x<b:

return f(x+1,b)+f(int(bin(x)[2:]+bin(x%5)[2:],2),b)

return 0

print(f(1,325))

Ответ: 53669

70)(№14419 Т.Закиров) Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить d

2. Умножить на 2

Первая команда увеличивает число на экране на d(d - натуральное число), вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Посчитали количество различных программ, для которых при исходном числе 1 результатом является число 100, и при этом траектория вычислений содержит число 10 и не содержит число 30.
Укажите общее количество таких программ при всех возможных d.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 и d = 1 траектория будет состоять из чисел 8, 16, 17.

Решение

Вариант 1 (t=0.0 c. - сам в шоке)

d,k=30,0

for dd in range(1,10):

a,b,c=1,10,100

m=[0]*(c+1)

m[a]=1

for p in [1,2]:

for i in range(a,b):

if i+dd<=b: m[i+dd]+=m[i]

if i*2<=b: m[i*2]+=m[i]

m[d]=0

a,b=b,c

k+=m[b]

print(k)

Вариант 2 (t=0.016 c.)

def f(a,b,d):

if a>b or a==30: return 0

if a==b: return 1

if a<b: return f(a+d,b,d)+f(a*2,b,d)

print(sum(f(1,10,i) * f(10,100,i) for i in range(1, 10)))

Ответ: 3349

71)(№5090 А.Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 1
2. Вычесть 2
3. Извлечь корень

Первые две команды уменьшают число на доске на 1 и 2 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 27 в число 6, содержат в траектории число 18, но не содержит число 20?

Решение

a,b,c=27,18,6

d=20

m=[0]*(a+1)

m[a]=1

for p in range(2):

for i in range(a,b,-1):

m[i-1]+=m[i]

if i-2>=b: m[i-2]+=m[i]

if i**0.5==int(i**0.5):m[int(i**0.5)]+=m[i]

m[d]=0

a,b=b,c

print(m[b])

Ответ: 3029

72)(№6036 И.Карпачев) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены коды:

A. Вычти 1
B. Вычти 2
С. Найди целую часть от деления на 2

Первая команда уменьшает число на экране на 1, вторая команда уменьшает число на экране на 2, третья команда заменяет число на экране на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 34 результатом будет являться число 2, при этом программа соответствует маске «?A*CB?» (символ «?» означает ровно один произвольный символ; символ «*» означает любую последовательность символов произвольной длины; в том числе «*» может задавать и пустую последовательность) и не содержит двух идущих подряд одинаковых команд?

Решение

def f(a,b,h):

if 'AA' in h or 'BB' in h or 'CC' in h: return 0

if a==b:

if h[1]+h[-3:-1]=='ACB':

return 1

else: return 0

if a<b: return 0

return f(a-1,b,h+'A')+f(a-2,b,h+'B')+f(a//2,b,h+'C')

print(f(34,2,''))

Ответ: 32

73)(№3715 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычесть 1
2. Обнулить

Первая команда уменьшает число на 1. Вторая команда обнуляет все ненулевые разряды, кроме старшего (например, для исходного числа 11101 результатом работы команды будет число 10000), если таких разрядов нет, то данная команда не выполняется.

Сколько существует программ, которые исходное двоичное число 1100 преобразуют в двоичное число 100?

Решение

a,b=int('1100',2),int('100',2)

m=[0]*(a+1)

m[a]=1

for i in range(a,b,-1):

m[i-1]+=m[i]

c=bin(i)[2:]

if c.count('1')>1 and int('1'+'0'*(len(c)-1),2)>=b: m[int('1'+'0'*(len(c)-1),2)]+=m[i]

print(m[b])

Ответ: 20

74)(№4038) Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Умножь на 2 и прибавь 1

Сколько различных результатов можно получить из исходного числа 3 после выполнения программы, содержащей ровно 11 команд?

Решение

Вариант 1 (t = 0.012 сек.)

def f(x,n):

if n==11: d.add(x)

else:f(x+1,n+1); f(x*2+1,n+1)

d=set();f(3,0);print(len(d))

Вариант 2 (t = 0.009 сек.)

m=[0]*8500

m[3]=1;a=b=3

for p in range(11):

m1=[0]*8500

a=0

for i in range(a,b+1):

if m[i]>0:

m1[i+1]=1

m1[i*2+1]=1

if a==0:a=i+1

b=i*2+1

m=m1[:]

Ответ: 820

75)(№ 6605 Е.Джобс) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Вычти 2
2. Раздели нацело на 2
3. Раздели нацело на 3

Выполняя первую из них, исполнитель уменьшает число на экране на 2, выполняя вторую – делит нацело на 2, выполняя третью – делит нацело на 3. Сколько существует программ, для которых при исходном числе 40 результатом является число 2, и при этом траектория вычислений не содержит число 22?

Решение

def f(x):

if x==2: return 1

if x<2 or x==22: return 0

return f(x-2)+f(x//2)+f(x//3)

print(f(40))

Ответ: 260

76)(№ 5214) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 1
2. Припиши 3

Первая команда увеличивает число на экране на 1, вторая приписывает 3 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 13, 14, 143. Сколько существует различных программ, которые преобразуют исходное число 3 в число 462?

Решение

Вариант 1 (t = 0.022 сек.)

def f(x):

if x==462: return 1

if x>462: return 0

else:return f(x+1)+f(x*10+3)

print(f(3))

Вариант 2 (t = 0.006 сек.)

a,b=3,462

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i*10+3<=b: m[i*10+3]+=m[i]

print(m[b])

Ответ: 260

77)(№3709 А.Комков) Исполнитель Нолик преобразует двоичное число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Добавить справа 0
3. Добавить справа 1

Первая команда увеличивает число на 1. При выполнении второй команды, исполнитель справа к числу приписывает 0, а при выполнении третьей команды справа к числу приписывает 1. (например, для числа 10 результатом работы данных команд будут являться числа 100 и 101 соответственно).

Сколько существует программ, которые исходное двоичное число 100 преобразуют в двоичное число 11101?

Решение

Переводим условие задачи в десятичную систему счисления

100 = 4, 11101 = 29,

добавить справа 0 = умножить на 2, добавить справа 1 = умножить на 2 + 1

def f(x):

if x==29: return 1

if x>29: return 0

return f(x+1)+f(x*2)+f(x*2+1)

print(f(4))

Ответ: 79

78)(№6172 М.Шагитов ) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 3
2. Умножь на 4
3. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. У исполнителя есть запас энергии, который в начальный момент равен 700. При выполнении каждой команды над текущим числом на экране исполнитель расходует энергию равную 10 единиц.

Сколько существует различных программ, преобразующих число 1 в число 4400, после выполнения которых запас энергии точно равен 0?

Решение

Вариант 1 (t = 1.0409 сек.)

from functools import *

@lru_cache(maxsize=None)

def f(x,e):

if e==0 and x==4400: return 1

elif e==0 or x>4400: return 0

return f(x+3,e-10)+f(x*4,e-10)+f(x*5,e-10)

print(f(1,700))

Вариант 2 (t = 1.2539 сек.)

from functools import *

@cache # оператор поддерживается версиями 3.9 и выше

def f(x,e):

if e==0 and x==4400: return 1

elif e==0 or x>4400: return 0

return f(x+3,e-10)+f(x*4,e-10)+f(x*5,e-10)

print(f(1,700))

Вариант 3 (t = 0.4239 сек.)

a,b=1,4400

m1=[0]*(b+1)

m1[a]=1

a1=b1=a

for p in range(70):

m2=[0]*(b+1)

bm=b1

for i in range(a1,b1+1):

if m1[i]>0:

if i+3<=b:m2[i+3]+=m1[i]

if i*4<=b:m2[i*4]+=m1[i]

if i*5<=b:m2[i*5]+=m1[i];bm=i*5

a1,b1=a1+3,bm

m1=m2[:]

print(m1[b])

Ответ: 1423

79)(№5156 Е.Джобс ) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавь 2
2. Вычти 3

Первая команда увеличивает число на экране на 2, вторая уменьшает на 3. При выходе за пределы отрезка [–40; 40] исполнитель аварийно завершает свою работу. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 30 и при этом траектория вычислений не содержит одинаковых чисел?

Решение

def f(x,m):

a=m[:]

if x==30: return 1

if x in a or x<-40 or x>40: return 0

a.append(x)

return f(x+2,a)+f(x-3,a)

print(f(1,[]))

Ответ: 851

80)(№6008 И.Карпачев) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены коды:

A. Прибавь 1
B. Умножь на 2
С. Умножь на 3

Первая команда увеличивает число на 1, вторая – умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом будет являться число 27, при этом программа содержит подпоследовательность команд BCA.

Решение

def f(x,p):

if x==27 and 'BCA' in p:return 1

if x>=27: return 0

return f(x+1,p+'A')+f(x*2,p+'B')+f(x*3,p+'C')

print(f(2,''))

Ответ: 5

81)(№7179 М.Шагитов) У исполнителя Калькулятор имеются три команды, которые обозначены латинскими буквами:

A. Прибавить 1
B. Прибавить 4
C. Умножить на 3

Найдите количество существующих программ, для которых при исходном числе 1 результатом является число 180, и при этом траектория вычислений содержит равное количество чисел, кратных трём, и чисел, кратных пяти. В ответе запишите сумму цифр этого числа.

Решение

Вариант 1 (t = 0.3954 сек.)

from functools import *

@lru_cache(maxsize=None)

def f(x,n3,n5):

if x%3==0:n3+=1

if x%5==0:n5+=1

if x==180 and n3==n5: return 1

if x>=180: return 0

return f(x+1,n3,n5)+f(x+4,n3,n5)+f(x*3,n3,n5)

print(sum(map(int,str(f(1,0,0)))))

Вариант 2 (t = 0.5014 сек.)

from functools import *

@cache # оператор поддерживается версиями 3.9 и выше

def f(x,n3,n5):

if x%3==0:n3+=1

if x%5==0:n5+=1

if x==180 and n3==n5: return 1

if x>=180: return 0

return f(x+1,n3,n5)+f(x+4,n3,n5)+f(x*3,n3,n5)

print(sum(map(int,str(f(1,0,0)))))

Ответ: 112

82)(№6088 Д.Муфаззалов) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

Первая из них увеличивает число на экране на 1, вторая - умножает его на 2. Программа для исполнителя – это последовательность команд.

При выполнении каждой команды с некоторым числом исполнитель тратит энергию, количество которой для каждых числа и команды приведено в таблице:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

прибавить 1 3 3 3 1 3 2 3 2 1 4 5 4 5 2 3

умножить на 2 1 4 2 2 2 1 2 3 2 3 4 3 4 3 2

Какое минимальное количество энергии может потратить исполнитель, преобразуя число 1 в число 16?

Решение

def f(x,w):

global minw

if x==16: minw=min(minw,w)

if x<16:f(x+1,w+m1[x]); f(x*2,w+m2[x])

m1=[0,3,3,3,1,3,2,3,2,2,4,5,4,5,2,3]

m2=[0,1,4,2,2,2,1,2,3,2,3,4,3,4,3,2]

minw=10**16

f(1, 0)

print(minw)

Ответ: 10

83)(№2499) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 3
3. Умножить на 3

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 15?

Решение

Вариант 1 (t = 0.017c.)

a,b=1,15

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

m[i+1]+=m[i]

if i+3<=b:m[i+3]+=m[i]

if i*3<=b:m[i*3]+=m[i]

print(m[b])

Вариант 2 (t = 0.016c.)

def f(x):

if x==15: return 1

if x>15: return 0

return f(x+1)+f(x+3)+f(x*3)

print(f(1))

Ответ: 230

84)(№5465 Е.Джобс) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычти 3
2. Раздели нацело на 2

Выполняя первую из них, исполнитель уменьшает число на экране на 3, выполняя вторую – делит число на экране на 2 нацело, отбрасывая остаток. Программой для исполнителя называется последовательность команд. Сколько существует программ, для которых при исходном числе 108 результатом является число 12, и при этом траектория вычислений содержит число 42?

Решение

Вариант 1 (t = 0.015c.)

a,b,c=108,42,12

m=[0]*(a+1)

m[a]=1

for p in range(2):

for i in range(a,b,-1):

if i-3>=b:m[i-3]+=m[i]

if i//2>=b:m[i//2]+=m[i]

a,b=b,c

print(m[c])

Вариант 2 (t = 0.016c.)

def f(a,b):

if a==b: return 1

if a<b: return 0

return f(a-3,b)+f(a//2,b)

print(f(108,42)*f(42,12))

Ответ: 30

85)(№4950) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 18 и при этом не содержат двух команд «Прибавить 1» подряд?

Решение

Вариант 1

a,b=1,18

m=[0]*(b+1)

m1=[0]*(b+1)

m[a]=1

for i in range(a,b):

m1[i+1]+=m[i]

if i+2<=b: m[i+2]+=m[i]+m1[i]

if i*2<=b: m[i*2]+=m[i]+m1[i]

print(m[b]+m1[b])

Вариант 2

def f(x,p):

if x==18: return 1

if x>18: return 0

if p==1: return f(x+2,2)+f(x*2,3)

else: return f(x+1,1)+f(x+2,2)+f(x*2,3)

print(f(1,0))

Ответ: 478

86)(№7100 М.Ишимов) У исполнителя Калькулятор имеются две команды, которые обозначены буквами:

A. Прибавить 2

B. Прибавить 4

Сколько существует программ, для которых при исходном числе 3 результатом является число 69, и при этом траектория вычислений содержит числа 9 и 61?

Решение

Вариант 1

a,b,c,d=3,9,61,69

m=[0]*(d+1)

m[a]=1

for p in range(3):

for i in range(a,b):

if i+2<=b: m[i+2]+=m[i]

if i+4<=b: m[i+4]+=m[i]

a,b,c=b,c,d

print(m[b])

Вариант 2

def f(x,y):

if x==y: return 1

if x>y:return 0

return f(x+2,y)+f(x+4,y)

print(f(3,9)*f(9,61)*f(61,69))

Ответ: 2946270

87)(№6527 А.Богданов) У исполнителя Цифрень имеются две команды, которым присвоены номера:

1. прибавь 1

2. прибавь 2

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2. Определим цифровой корень числа как сумму цифр числа, которая вычисляется рекурсивно до тех пор, пока не останется одна цифра. Например, для числа 1993 цифровой корень вычисляется как 1+9+9+3 = 22 => 2+2 = 4.

Сколько существует различных программ, преобразующих число 12 в число 37 и не содержащих команд, в которых цифровой корень исходного числа равен младшей цифре числа-результата? Например, к числу 18 (цифровой корень 9) можно применить команду 2, так что получим 20 (9 ≠ 0). Но к числу 20 (цифровой корень 2) команду 2 применить нельзя, так как последняя цифра результата 22, равная 2, совпадает с цифровым корнем исходного числа.

Решение

def fk(x):

while x>9:

x=sum(map(int,str(x)))

return x

a,b=12,37

m=[0]*(b+1)

m[a]=1

for i in range(a,b):

if fk(i)!=(i+1)%10: m[i+1]+=m[i]

if fk(i)!=(i+2)%10 and i+2<=b: m[i+2]+=m[i]

print(m[b])

Ответ: 55