Количество программ из A в B смешанное —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#75079

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

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

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

3. Умножь на 2

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

Показать ответ и решение

def f(a,b):
    if a > b or a == 7:return 0
    if a == b:return 1
    return f(a+1,b)+f(a+2,b)+f(a*2,b)
print(f(2,30)*f(30,41))

Ответ: 58667328

Ошибка.
Попробуйте повторить позже

Задача 2#72464

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

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

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

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

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

Показать ответ и решение

def f(a,b):
    if a > b or a == 15:return 0
    if a == b:return 1
    return f(a+1,b)+f(a+4,b)+f(a*2,b)
print(f(2,7)*f(7,30))

Ответ: 2900

Ошибка.
Попробуйте повторить позже

Задача 3#72447

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

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

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

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

Показать ответ и решение

def f(a,b):
    if a > b or a == 20:return 0
    if a == b:return 1
    return f(a+1,b)+f(a*2,b)
print(f(8,5)*f(5,36))

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 4#72436

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

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

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

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

Показать ответ и решение

def f(a,b):
    if a > b or a == 12:return 0
    if a == b:return 1
    return f(a+1,b)+f(a+2,b)
print(f(3,6)*f(6,21))

Ответ: 816

Ошибка.
Попробуйте повторить позже

Задача 5#63539

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

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

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

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

Показать ответ и решение

def f(n, m):
    if n == m:
        return 1
    if n > m or n == 12:
        return 0
    if n < m:
        return f(n+1, m) + f(n*2, m)
print(f(3, 18) * f(18, 55))

Ответ: 88

Ошибка.
Попробуйте повторить позже

Задача 6#63352

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

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

Показать ответ и решение

def F(x, y):
    if x == y: return 1
    if x > y or x==8 or x ==15: return 0
    if x < y: return F(x+1, y) + F(x+2, y) + F(x*3, y)
print(F(3, 10)*F(10,22))

Ответ: 390

Ошибка.
Попробуйте повторить позже

Задача 7#60496

Исполнитель КотПесДруг преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

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

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

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

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

Показать ответ и решение

def f(n, m):
    if n == m:
        return 1
    if n > m or n == 20:
        return 0
    return f(n+2, m)+f(n+6, m)+f(n*3, m)

# Сначала доходим до 14, потом из 14 до 42, перемножаем траектории
print(f(4, 14)*f(14, 42))

Ответ: 240

Ошибка.
Попробуйте повторить позже

Задача 8#60491

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

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

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

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

Показать ответ и решение

def f(n, m):
    if n == m:
        return 1
    if n > m or n == 31:
        return 0
    return f(n+1, m)+f(n+5, m)

# Сначала доходим до 21, потом из 21 до 66, перемножаем траектории
print(f(1, 21)*f(21, 66))

Ответ: 11490780

Ошибка.
Попробуйте повторить позже

Задача 9#58981

Исполнитель Сова преобразует число на экране.

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

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

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

3. Сделать нечетное (умножить на два и вычесть 1)

Первая команда увеличивает число на экране на 2, вторая увеличивает его в 3 раза, третья увеличивает в два раза и уменьшает на один. Программа для исполнителя Сова — это последовательность команд.

Сколько существует программ, для которых при исходном числе 5 результатом является число 37, и при этом траектория вычислений содержит число 17 и не содержит число 21? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 1 траектория будет состоять из чисел 3, 5, 15.

Показать ответ и решение

def f(a,b):
    if a > b or a == 21:return 0
    if a == b:return 1
    if a < b:return f(a+2,b) + f(a*3,b) + f(a*2-1,b)
print(f(5,17)*f(17,37))

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 10#58508

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

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

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

Программа для исполнителя Исполнятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 45, и при этом траектория вычислений содержит числа 11 и 21 и не содержит число 15?

Показать ответ и решение

a = [0] * 100
a[3] = 1
for i in range(4, 46):
    a[i] = a[i - 2] + a[i // 5] * (i % 5 == 0)
    a[15] = 0
    if i == 11 or i == 21:
        for j in range(i):
            a[j] = 0
print(a[45])

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 11#58506

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

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

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

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

Показать ответ и решение

a = [0] * 100
a[3] = 1
for i in range(4, 25):
    a[i] = a[i - 1] + a[i - 2]
    a[14] = 0
    if i == 11:
        for j in range(i):
            a[j] = 0
print(a[24])

Ответ: 3740

Ошибка.
Попробуйте повторить позже

Задача 12#58505

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

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

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

Программа для исполнителя Крутая – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 49, и при этом траектория вычислений содержит число 13 и не содержит число 29?

Показать ответ и решение

a = [0] * 100
a[4] = 1
for i in range(5, 50):
    a[i] = a[i - 1] + a[i - 9]
    a[29] = 0
    if i == 13:
        for j in range(i):
            a[j] = 0
print(a[49])

Ответ: 538

Ошибка.
Попробуйте повторить позже

Задача 13#58504

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

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

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

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

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

Показать ответ и решение

a = [0] * 100
a[2] = 1
for i in range(3, 62):
    a[i] = a[i - 1] + a[i - 10] + a[i // 2] * (i % 2 == 0)
    a[39] = 0
    if i == 18:
        for j in range(i):
            a[j] = 0
print(a[61])

Ответ: 27800

Ошибка.
Попробуйте повторить позже

Задача 14#57289

Геральт копит чеканные монеты, количество которых записано на экране.

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

1. Прибавить 5 монет, убив утопца,

2. Прибавить 10 монет, выполнив заказ на призрака,

3. Увеличить количество монет в 2 раза, сыграв в гвинт.

Первый вариант учеличивает количество монет на 5, второй — на 10, третий — умножает количество монет на 2. Программа для Геральта из Ривии — это последовательность вариантов.

Геральту нужно накопить 100 монет, чтобы выкупить Лютика из плена эльфов.

Сколько существует программ, для которых при исходном количестве монет 15 является результатом 100 монет. При этом траектория вычислений содержит любимое число Геральта — 50 и не содержит числа 25 и 40? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 12, 22, 44.

Показать ответ и решение

def f(a,b):
    if a > b or a == 25 or a == 40 :return 0
    if a == b:return 1
    if a < b:return f(a+5,b)+f(a+10,b)+f(a*2,b)
print(f(15,50)*f(50,100))

Ответ: 180

Ошибка.
Попробуйте повторить позже

Задача 15#57111

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

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

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

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

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

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

Показать ответ и решение

a = [0] * 100
a[2] = 1
for i in range(3, 35):
    a[i] = a[i - 2] + a[i - 6] + a[i // 2] * (i % 2 == 0)
    a[26] = 0
    if i == 14:
        for j in range(i):
            a[j] = 0
print(a[34])

Ответ: 208

Ошибка.
Попробуйте повторить позже

Задача 16#56459

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

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

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

Показать ответ и решение

def f(s):
    a = s[-1]
    if len(s) > 1 and a == 12:
        return 1
    if a < 10 or a > 30 or (a in s[:-1]):
        return 0
    return sum(f(s + [a + h]) for h in [2, 1, -3])


print(f([20]))

Ответ: 284

Ошибка.
Попробуйте повторить позже

Задача 17#52528

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

Показать ответ и решение

a = [0] * 29
a[1] = 1
for i in range(2, 29):
    a[i] = a[i - 1] + a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
    a[10], a[11] = 0, 0
    if i == 8:
        for j in range(8):
            a[j] = 0
print(a[28])

Ответ: 186

Ошибка.
Попробуйте повторить позже

Задача 18#52527

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

Показать ответ и решение

a = [0] * 23
a[3] = 1
for i in range(4, 23):
    a[i] = a[i - 1] + a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
    a[8], a[15] = 0, 0
    if i == 10:
        for j in range(10):
            a[j] = 0
print(a[22])

Ответ: 390

Ошибка.
Попробуйте повторить позже

Задача 19#6868

Исполнитель преобразует число, записанное на экране.

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

Прибавить 2,

Прибавить 3,

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

Первая команда увеличивает число на экране на 2, вторая увеличивает на 3, третья увеличивает число на экране в 2 раза. Программа для— это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 6 и 9, но не содержит число 13? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 12, 24.

Показать ответ и решение

Пусть $R (n)$ — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

$R(n ) = R (n − 2) + R (n − 3)$ — если число не делится на 2.

$R(n ) = R (n − 2) + R (n − 3) + R (n : 2)$ — если число делится на 2.

Заполним таблицу по данной формуле до 6:

|--|--|--|--|--|--| |1-|2-|3-|4-|5-|6-| |1 |1 |1 |3 |2 |5 | -------------------

Так как по условию сказано, что траектория должна содержать число 6, значит последующие числа мы можем получать только из 6. Продолжим заполнять таблицу:

|--|--|--|--|---|--|--|--|--| |1 |2 |3 |4 |5 |6 |7 |8 |9 | |--|--|--|--|---|--|--|--|--| -1--1--1--3--2---5--0--5--5-|

Аналогично с 9. Сразу можно сказать, что число 13 нельзя никак получить, так как по условию траектория не должна через него проходить. Значит $R (13) = 0$ . Заполним таблицу до конца:

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

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 20#6867

Исполнитель преобразует число, записанное на экране.

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 33 и при этом траектория вычислений содержит число 12 и не содержит число 27? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 231 при исходном числе 6 траектория будет состоять из чисел 9, 27, 28.

Показать ответ и решение

Пусть $R (n)$ — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение: