Количество программ из A в B (Стандартные задачи) —Каталог задач по ЕГЭ - Информатика

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

Задача 1#30470

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

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

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

...

n. Умножить на n, где n — число, на котором находится исполнитель. Если исполнитель применяет команды к числу 2, то он может умножить на 2, если число 3, то от 2 до 3 и т.д.

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

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

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

Решение 1 (Рекурсия)

def f(st, fn):
    if st == fn:
        return 1
    if st > fn:
        return 0
    a = [0] * (st * st)
    for i in range(2, st + 1):
        a[i] = f(st * i, fn)
    return sum(a)
print(f(2, 60))

Решение 2 (Динамика)

a = [0] * 60 * 60
a[2] = 1
for i in range(2, 60):
    for j in range(2, i + 1):
        a[i * j] += a[i]
print(a[60])

Ответ: 1

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

Задача 2#30469

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

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

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

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

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

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

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

Решение 1 (Рекурсия)

def f(st, fn):
    if st == fn:
        return 1
    if st > fn:
        return 0
    return f(st + 1, fn) + f(st + 2, fn) + f(st * 4, fn)
print(f(2, 25))

Решение 2 (Динамика)

a = [0] * 26
a[2] = 1
for i in range(3, 26):
    a[i] = a[i - 2] + a[i // 4] * (i % 4 == 0) + a[i - 1]
print(a[25])

Решение 3 (Динамика)

a = [0] * 150
a[2] = 1
for i in range(2, 25):
    a[i + 1] += a[i]
    a[i + 2] += a[i]
    a[i * 4] += a[i]
print(a[25])

Ответ: 49468

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

Задача 3#29458

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

1. Прибавь $5$

2. Прибавь $8$

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

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

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

Решение 1 (Рекурсия)

def f(s, fi):
    if s > fi:
        return 0
    if s == fi:
        return 1
    return f(s + 5, fi) + f(s + 8, fi)
print(f(2, 128))

Решение 2 (Динамика)

a = [0] * 129
a[2] = 1
for i in range(3, 129):
    a[i] += a[i - 5] + a[i - 8]
print(a[128])

Ответ: 135120

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

Задача 4#28005

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

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

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

3. Умножь сам на себя (возвести в квадрат)

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

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

a = [0]*39
a[2] = 1
for i in range(3, 39):
    a[i] = a[i-1] + a[i//2]*(i % 2 == 0) + \
        a[int(i**0.5)] * (i**0.5 == int(i**0.5))
print(a[38])

Ответ: 266

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

Задача 5#26958

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

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $1$ траектория будет состоять из чисел $2,4,5.$

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

a = [0] * 1000
a[1] = 1
for i in range(10):
    a[i+1] += a[i]
    a[i+2] += a[i]
print(a[10])

Ответ: 55

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

Задача 6#26156

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

1. Прибавь 1

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

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

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

a = [0] * 28
a[11] = 1
for i in range(12, 28):
    a[i] = a[i-1] + a[i-10]
print(a[27])

Ответ: 8

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

Задача 7#26102

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

Прибавь $1$
Увеличь число десятков на $1$

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

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

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

Решение 1 (Рекурсия)

def f(a, b):
    if a > b:
        return 0
    if a == b:
        return 1
    return f(a + 1, b) + f(a + 10, b)

print(f(12, 36))

Решение 2 (Динамика)

a = [0] * 37
a[12] = 1
for i in range(13, 37):
    a[i] += a[i - 1]
    a[i] += a[i - 10]
print(a[36])

Ответ: 31

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

Задача 8#26075

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

Вычесть $1$ ;
Вычесть $3$ ;
Разделить нацело на $3$ .

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

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

Решение 1 (Динамика)

a = [0] * 70
a[22] = 1
for i in range(21, 1, -1):
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
print(a[2])

Решение 2 (Рекурсия)

def f(a, b):
    if a == b:
        return 1
    if a < b:
        return 0
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

print(f(22, 2))

Решение 3 (Динамика)

a = [0] * 23
a[22] = 1
for i in range(22, 2, -1):
    a[i // 3] += a[i]
    a[i - 3] += a[i]
    a[i - 1] += a[i]
print(a[2])

Ответ: 2196

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

Задача 9#25969

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

Прибавь $2$
Прибавь $3$
Прибавь предыдущее

Первая команда увеличивает число на экране на $2$ , вторая увеличивает это число на $3$ , третья прибавляет к числу на экране число, меньшее на $1$ (к числу $3$ прибавляется $2$ , к числу $11$ прибавляется $10$ и т. д.). Программа для исполнителя — это последовательность команд.

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

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

Решение №1

a = [0] * 12
a[2] = 1
for i in range(3, 12):
    a[i] = a[i-2] + a[i-3] + a[i//2 + 1] * (i % 2)
print(a[11])

Решение №2

a = [0] * 11 * 2
a[2] = 1
for i in range(2, 11):
    a[i + 2] += a[i]
    a[i + 3] += a[i]
    a[i + i - 1] += a[i]
print(a[11])

Ответ: 17

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

Задача 10#24424

Исполнитель АИ решает $23$ -и задачи. Когда он выбирает, сколько еще задач он хочет решить, он выполняет одно из двух действий:

Увеличить количество решенных задач на $1$
Решить еще столько задач, чтобы суммарное число уже решенных задач увеличилось в $1.5$ раза. Действие допустимо, если АИ уже решил четное количество задач.

Пока что АИ решил только $1$ задачу. Сколькими способами АИ может сделать так, чтобы число решенных задач стало равно $20$ ?

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

Решение 1 (Рекурсия)

def f(s, fi):
    if s > fi:
        return 0
    if s == fi:
        return 1
    if s % 2 != 0:
        return f(s + 1, fi)
    else:
        return f(s + 1, fi) + f(s * 1.5, fi)
print(f(1, 20))

Решение 2 (Динамика)

a = [0] * 21
a[1] = 1
for i in range(2, 21):
    a[i] = a[i - 1] + a[i - i // 3] * (i % 3 == 0)
print(a[20])

Ответ: 32

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

Задача 11#23510

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

Прибавить $1$ ;
Умножить на $4$ .

Программа для исполнителя Крабика — это последовательность команд. Сколько существует программ, которые число $1$ преобразуют в число $55$ ?

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

Решение 1

a = [0] * 56
a[1] = 1
for i in range(2, 56):
    a[i] = a[i - 1] + a[i // 4] * (i % 4 == 0)
print(a[55])

Решение 2

a = [0] * 55 * 4 + 1
a[1] = 1
for i in range(1, 55):
    a[i + 1] += a[i]
    a[i * 4] += a[i]
print(a[55])

Ответ: 32

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

Задача 12#22216

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

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

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

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

Первая команда увеличивает число на экране на 2, вторая $−$ на 5.

Сколько существует программ, для которых при исходном числе 1 результатом является число 19? Траектория вычислений программы $−$ это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 1 траектория будет состоять из чисел 3, 8, 10.

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

num = [0]*20
num[1] = 1
for i in range(2, 20):
num[i] = num[i-2]+num[i-5]*(i > 5)
print(num[19])

Ответ: 16

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

Задача 13#22215

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая $−$ на 3.

Сколько существует программ, для которых при исходном числе 4 результатом является число 30? Траектория вычислений программы $−$ это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 1 траектория будет состоять из чисел 2, 5, 6.

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

num = [0]*31
num[4] = 1
for i in range(5, 31):
num[i] = num[i-1]+num[i-3]
print(num[30])

Ответ: 12664

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

Задача 14#22214

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

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

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

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

Первая команда увеличивает число на экране на $1$ , вторая — на $10$ .

Сколько существует программ, для которых при исходном числе $7$ результатом является число $49$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

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

num = [0]*60
num[7] = 1
for i in range(8, 60):
    num[i] = num[i-1] + num[i-10]
print(num[49])

Ответ: 780

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

Задача 15#16518

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

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

Прибавить $1$ ;
Прибавить $4$ .

Первая команда увеличивает число на экране на $1$ , вторая — на $4$ .

Сколько существует программ, для которых при исходном числе $1$ результатом является число $128$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $1$ траектория будет состоять из чисел $2,6,7$ .

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

  num = [0]*129
  num[1] = 1
  for i in range(2, 129):
      num[i] = num[i-1]+num[i-4]
  print(num[128])

Ответ: 326671493536033573

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

Задача 16#16516

Исполнитель ГИРЛЯНДА преобразует число, записанное на экране.

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

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

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

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

Сколько существует программ, для которых при исходном числе 4 результатом является число 30? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 1 траектория будет состоять из чисел 2, 5, 6.

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

  num = [0]*31
  num[4] = 1
  for i in range(5, 31):
      num[i] = num[i-1]+num[i-3]
  print(num[30])

Ответ: 12664

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

Задача 17#16514

Исполнитель ЕЛОЧКА преобразует число, записанное на экране.

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

Прибавить $1$
Прибавить $10$

Первая команда увеличивает число на экране на $1$ , вторая — на $10$ .

Сколько существует программ, для которых при исходном числе $7$ результатом является число $49$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

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

Решение 1

num = [0]*50
num[7] = 1
for i in range(8, 50):
num[i] = num[i-1] + num[i-10]
print(num[49])

Решение 2

a = [0] * 60
a[7] = 1
for i in range(7, 50):
a[i + 1] += a[i]
a[i + 10] += a[i]
print(a[49])

Ответ: 780

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

Задача 18#16435

Дед Мороз написал программу для исполнителя ЮП, который преобразовывает числа. У исполнителя ЮП две команды, которым присвоены номера:

1. прибавь 1,

2. прибавь 3.

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

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

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

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

    a = [0]*50
    a[5] = 1
    for i in range(6,43):
        a[i] = a[i-1]+a[i-3]
    print(a[42])

Ответ: 848491

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

Задача 19#12828

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

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

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

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

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

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

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

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

В четные числа мы можем попасть из числа деленного на 2 или предыдущего, а в нечетные только из предыдущих.
Получается, что в число 2 мы можем попасть из 1 двумя разными способами.
В число 3 мы можем попасть только из 2.
В число 4 мы можем попасть из 2 или 3.
В число 5 мы можем попасть только из 4.
И т.д.

Ответ: 36

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

Задача 20#11525

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

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

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

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

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

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

a = [0] * 11
a[1] = 1
for i in range(2, 11):
    a[i] = a[i-1] + a[i-2]
print(a[10])

Ответ: 55