Прочие прототипы —Каталог задач по ЕГЭ - Информатика БУ

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

Задача 1#22904

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

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

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

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

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

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

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

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 2, y) + f(x + 4, y) + f(x + 5, y)

for y in range(32, 70):
    if f(31, y) == 1001:
        print(y)

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

a = [0] * 100
a[31] = 1
for i in range(32, 100 + 1):
    a[i] = a[i-2] + a[i-4] + a[i-5]
    if a[i] == 1001:
        print(i)
        break

Ответ: 56

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

Задача 2#26690

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

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

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

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

Найдите длину самой короткой программы, в результате выполнения которой при исходном числе $1$ результатом является число $227$ .

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

a = [0] * 300
a[0] = 10**20
a[1] = 0
for i in range(2, 300):
    x, y, z = 10**10, 10**10, 10**10
    x = a[i - 1] + 1
    if i >= 5:
        y = a[i - 5] + 1
    if i % 3 == 0:
        z = a[i // 3] + 1
    a[i] = min(x, y, z)
print(a[227])

Ответ: 7

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

Задача 3#27466

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

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

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

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

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

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

for i in range(6, 100):
    if f(5, i) == 34:
        print(i)
        break

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

a = [0] * 101
a[5] = 1
for i in range(6, 101):
    a[i] += a[i - 2] + a[i - 5]
print(a.index(34))

Ответ: 27

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

Задача 4#30474

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

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

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

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

В какое минимальное число мог направиться исполнитель из числа $1$ , если до пункта назначения он добрался с помощью $36$ различных программ.

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

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

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y)

a = set()
for y in range(2, 100):
    if f(1, y) == 36:
        a.add(y)
        
print(min(a))

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

a = [0] * 100
a[1] = 1

for i in range(1, 30):
    a[i + 1] += a[i]
    a[i * 2] += a[i]

print(a.index(36))

Ответ: 16

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

Задача 5#30485

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

1. Приписать 0 справа (1 $→$ 10)

2. Приписать копию числа задом наперед справа (10 $→$ 1001)

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

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

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

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

def f(st):
    global count
    if len(st) == 10:
        count += 1
        print(st)
    if len(st) < 10:
        f(st + "0") # приписать 0 справа
        f(st + st[::-1]) # приписать копию числа справа
count = 0
f("7")
print(count)

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

ans = []
otv = 0
ans.append("7")
for operations in range(1000):
    can_get = []
    for i in ans:
        if len(i) == 10:
            otv += 1
        new_st = i + "0"
        if len(new_st) <= 10:
            can_get.append(new_st)
        new_st = i + i[::-1]
        if len(new_st) <= 10:
            can_get.append(new_st)
    if len(can_get) == 0:
        break
    ans = can_get

print(otv)

Ответ: 14

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

Задача 6#30486

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

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

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

3. Приписать любую цифру от 0 до 9 справа (1 $→$ 10, или 1 $→$ 11, или 1 $→$ 12 и т.д.)

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

Сколько существует программ, для которых при исходном числe 1 результатом является число 48, при этом команда 3 встречается в программе чаще чем команда 2? Примеры программ: 33312 — True, 312 — False

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

Стоит сказать, что динамическое решение получается довольно трудоемким и громоздким, поэтому рекомендуется использовать рекурсивную реализацию в данной задаче.

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

def f(st, fn, count_2, count_3):
    if st == fn and count_3 > count_2:
        return True
    if st > fn:
        return False
    x = f(st + 3, fn, count_2, count_3)
    y = f(st * 2, fn, count_2 + 1, count_3)
    z = [0] * 10
    for i in range(10):
        z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
    return x + y + sum(z)
print(f(1, 48, 0, 0))

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

ans = set()
ans.add((1, 0, 0))  # (куда пришли, сколько раз использовали вторую команду, раз использовали третью команду)
otv = 0
for operations in range(1000):
    can_get = set()
    for i in ans:
        a, cnt_2, cnt_3 = i
        if (a == 48) and (cnt_2 < cnt_3):
            otv += 1
            continue
        if a + 3 <= 48:
            can_get.add((a + 3, cnt_2, cnt_3))
        if a * 2 <= 48:
            can_get.add((a * 2, cnt_2 + 1, cnt_3))
        for j in range(9):
            new_numb = int(str(a) + str(j))
            if new_numb <= 48:
                can_get.add((new_numb, cnt_2, cnt_3 + 1))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Ответ: 6

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

Задача 7#30487

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

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

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

3. Прибавить сумму цифр числа

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

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

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

from functools import lru_cache
@lru_cache(None)
def sum_of_digits(number):
    if number == 0:
        return 0
    else:
        return number % 10 + sum_of_digits(number // 10)

def f(a, b):
    if a == b:
        return 1
    elif a > b:
        return 0
    else:
        return f(a + 1, b) + f(a * 3, b) + f(a + sum_of_digits(a), b)

print(f(11, 60))

Ответ: 66173

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

Задача 8#30488

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

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

2. Вычесть 5

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

Сколько существует программ, для которых при исходном числe 1 результатом является число 20. При этом исполнитель не может посетить одно и то же число дважды и может двигаться пока не перейдет границы отрезка [-20; 40], при переходе границ исполнитель разрушается.

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

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

def f(start, finish, limits, visited):
    if (start == finish):
        return 1
    if (start < limits[0]) or (start > limits[1]):
        return 0
    if (start in visited):
        return 0
    vis = visited.copy()
    vis.add(start)
    x = f(start + 4, finish, limits, vis)
    y = f(start - 5, finish, limits, vis)
    return x + y
print(f(1, 20, (-20, 40), set()))

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

ans = []
ans.append((1, set([1])))
otv = 0
for operations in range(1000):
    can_get = []
    for i in ans:
        a, vis = i
        vis_first = vis.copy()
        vis_second = vis.copy()
        if a == 20:
            otv += 1
            continue
        if ((a + 4) in vis) == 0 and (a + 4 <= 40):
            vis_first.add(a + 4)
            can_get.append((a + 4, vis_first))
        if ((a - 5) in vis) == 0 and (a - 5 >= -20):
            vis_second.add(a - 5)
            can_get.append((a - 5, vis_second))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)

Ответ: 5495

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

Задача 9#30489

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

1. Приписать 1 справа (1 $→$ 11)

2. Приписать бит четности справа, если это 0, слева, если это 1 (бит четности — количество нулей в числе по модулю 2, 10 $→$ 110, 100 $→$ 1000)

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

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

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

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

def f(st, fn):
    if st == fn:
        return 1
    if len(st) > len(fn):
        return 0
    x = f(st + "1", fn)
    if st.count("0") % 2 == 0:
        y = f(st + "0", fn)
    else:
        y = f("1" + st, fn)
    return x + y


print(f("1", "1011111"))

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

def to_bin(n):  # перевод из десятичной СС в двоичную
    a = ""
    while n > 0:
        a = str(n % 2) + a
        n //= 2
    return a


# Если s="1010", то команда n=int(s, base=2) переводит число 1010
# из 2-й СС в 10-ю СС
a = [0] * 96
a[1] = 1
for i in range(1, 95):
    cur_num = to_bin(i)
    new_num = int(cur_num + "1", base=2)
    if new_num < 96:
        a[new_num] += a[i]
    chet_bit = cur_num.count("0") % 2
    if chet_bit:
        new_num = int("1" + cur_num, base=2)
    else:
        new_num = int(cur_num + "0", base=2)
    if new_num < 96:
        a[new_num] += a[i]
print(a[95])

Ответ: 1

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

Задача 10#30491

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

1. Прибавить 2 к координате X ((1, 2) $→$ (3, 2))

2. Умножить координату X на 2 ((1, 2) $→$ (2, 2))

3. Переместиться вверх на любое количество клеток от 1 до разницы между нынешней координатой и стеной, (стеной считается прямая y = «значение Y у конечной точки»)

Пример для команды 3, y = 5 — стена, ((1, 1) $→$ (1, 2), или (1, 1) $→$ (1, 3), или ..., или (1, 1) $→$ (1, 5))

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

Сколько существует различных программ, которые приведут исполнителя из точки с координатами (1, 2) в точку с координатами (12, 19).

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

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

from functools import lru_cache
@lru_cache(None)
def f(st, fn):
    if st == fn:
        return 1
    if st[0] > fn[0] or st[1] > fn[1]:
        return 0
    c1 = f((st[0] + 2, st[1]), fn)
    c2 = f((st[0] * 2, st[1]), fn)
    c = [0] * (fn[1] - st[1] + 1)
    for i in range(1, fn[1] - st[1] + 1):
        c[i] = f((st[0], st[1] + i), fn)
    return c1 + c2 + sum(c)
print(f((1, 2), (12, 19)))

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

dp = [[0] * 20 for i in range(13)]
dp[1][2] = 1
for x in range(1, 13):
    for y in range(2, 20):
        if x + 2 < 13:
            dp[x + 2][y] += dp[x][y]
        if x * 2 < 13:
            dp[x * 2][y] += dp[x][y]
        for to in range(y + 1, 20):
            dp[x][to] += dp[x][y]
print(dp[12][19])

Ответ: 1629356032

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

Задача 11#30492

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

1. Прибавить 3 камушка в кучу

2. Умножить количество камушков в куче на 2 и вычесть 1

3. Если количество камней в куче больше 9, то реверсировать количество камней в куче и прибавить 1 (10 $→$ 2 , 123 $→$ 322)

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

Какое минимальное количество команд содержит программа, которая проходит через 8 различных простых чисел. Исполнитель начинает с числа 2 (первое число тоже считается, если оно простое)

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

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

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n > 1


def f(st, count_operation, set_prime):
    global count
    if count_operation > count:
        return  # выход из программы без действий
    if is_prime(st):
        set_prime.add(st)
    if len(set_prime) == 8:
        count = min(count, count_operation)
        return
    f(st + 3, count_operation + 1, set_prime.copy())
    f(st * 2 - 1, count_operation + 1, set_prime.copy())
    if st > 9:
        f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy())


count = 10000000000
f(2, 0, set())
print(count)

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

def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1


primes = [0] * 100000
# для начала определим для каждого числа от 1 до 99999
# простое оно, или нет
for i in range(2, 100000):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
ans = []
ans.append((2, 1))
otv, flag = 100000000, 0

for operations in range(1000):
    can_get = []
    for i in ans:
        a, pr = i
        if pr == 8:
            otv = operations
            flag = 1
            break
        can_get.append((a + 3, pr + primes[a + 3]))
        can_get.append((a * 2 - 1, pr + primes[a * 2 - 1]))
        if a > 9:
            s = str(a)
            s = s[::-1]
            new_num = int(s) + 1
            can_get.append((new_num, pr + primes[new_num]))
    if flag:
        break
    ans = can_get
                                                                                                     
                                                                                                     
print(otv)

Ответ: 10

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

Задача 12#30493

Исполнитель Щелчок находится на первой ступеньке очень длинной лестницы. У исполнителя есть 3 команды:

1. Подняться на одну ступеньку и потратить одну единицу энергии.

2. Перешагнуть через одну ступеньку (подняться на две) и потратить 3 единицы энергии

3. Перешагнуть через две ступеньки (подняться на 3 ступеньки) и потратить 6 единиц энергии

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

У исполнителя в запасе 60 единиц энергии, длина лестницы 25 ступенек. За какое минимальное количество команд исполнитель сможет добраться до последней ступеньки и сохранить максимальный для такого количества команд запас энергии. Если запас энергии исполнителя кончается, он отчаивается и не идет дальше, кроме случая, если он уже на 25 ступеньке. В ответе укажите количество команд и максимальный сохраненный запас энергии.

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

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

from functools import lru_cache
@lru_cache(None)
def f(st, fn, en, comand):
    global count, ener
    if st == fn and en >= 0:
        if comand < count:
            count = comand
            ener = en
#если количество шагов совпало,
# то мы берем максимум энергии
        elif comand == count and en > ener:
            ener = en
        return # вылет из программы
    if en < 0:
        return
    f(st + 1, fn, en - 1, comand + 1)
    f(st + 2, fn, en - 3, comand + 1)
    f(st + 3, fn, en - 6, comand + 1)
count = 10000000
ener = -1
f(1, 25, 60, 0)
print(count, ener)

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

ans = []
ans.append((1, 60, 0))
# (текущая ступенька, текущее кол-во энергии, кол-во сделанных ходов)
otv, mn_com = -100000000, 100000000
for operations in range(1000):
    can_get = []
    for i in ans:
        step, energy, go = i
        if (step > 25) or (energy < 0):
            continue
        if (step == 25) and (energy >= 0):
            if mn_com == go:  # берем минимум команд и максимум энергии
                mn_com = go
                otv = max(otv, energy)
                continue
            elif mn_com > go:
                mn_com = go
                otv = energy
                continue
        # все возможные ходы
        can_get.append((step + 1, energy - 1, go + 1))
        can_get.append((step + 2, energy - 3, go + 1))
        can_get.append((step + 3, energy - 6, go + 1))
    # если больше ходов нет, выходим из цикла
    if len(can_get) == 0:
        break
    ans = can_get.copy()
print(mn_com, otv)

Ответ: 8 12

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

Задача 13#30494

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

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

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

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

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

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

Исполнитель хочет выяснить какое минимальное количество простых чисел он может посетить при перемещении из числа 10 в число 300.

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

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

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

from functools import lru_cache
@lru_cache(None)
def f(st, fn, primes):
    global count
    if is_prime(st):
        primes += 1
    if st == fn:
        if primes < count:
            count = primes
        return
    if st > fn:
        return
    f(st + 1, fn, primes)
    f(st * 2 + 1, fn, primes)
    f(st * 2 - 1, fn, primes)
    f(st * 4 + 1, fn, primes)

count = 100000000000
f(10, 300, 0)
print(count)

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

def is_prime(n):
    if n < 2:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return 0
    return 1


a, primes = [10000000] * 301, [0] * 301
a[10] = 0
# для начала определим для каждого числа от 1 до 300
# простое оно, или нет
for i in range(2, 301):
    if is_prime(i):
        primes[i] = 1
# далее реализуем динамическое решение задачи
for i in range(10, 300):
    a[i + 1] = min(a[i + 1], a[i] + primes[i + 1])
    if i * 2 + 1 < 301:
        a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1])
    if i * 2 - 1 < 301:
        a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1])
    if i * 4 + 1 < 301:
        a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1])
print(a[300])

Ответ: 2

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

Задача 14#37825

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

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

2. Раздели на $2.$

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

Программа для Хитрителя — это последовательность команд. Сколько есть программ, которые применяют вторую команду не более $4$ раз и преобразуют число $10$ в число $20$ ?

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

Ключевое замечание, необходимое для решения задачи — заметим, что нет смысла рассматривать числа большие $16⋅20,$ так как из них даже четырежды применив вторую операцию не получится получить число $20$ . Далее достаточно написать $dp[i][cnt]$ — количество программ заканчивающихся в числе $i$ и при этом использующие ровно $cnt$ шагов второго типа. База динамики $dp[10][0] = 1$ . Переход в динамике: $dp[x][cnt] = dp[x - 1][cnt] + dp[2 * x][cnt - 1]$ . Конечно стоит аккуратно проверять, что $x− 1 ≥ 0, 2x ≤ 16⋅20, cnt− 1 ≥ 0$ .

Решение на C++

void solve(){
    //dp[x][cnt] - количество программ приводящие в число x,
    //и при этом использовали ровно cnt операций второго типа
    vector<vector<int>> dp(16 * 20 + 1, vector<int>(5, 0));
    dp[10][0] = 1;
    for(int cnt = 0; cnt < 5; ++cnt){
        for(int x = 0; x <= 16 * 20; ++x){
            if(x + 1 < 16 * 20 + 1) //операция прибавить 1
         dp[x + 1][cnt] += dp[x][cnt];
            if(x % 2 == 0 && cnt + 1 < 5) //операция разделить на 2
                dp[x / 2][cnt + 1] += dp[x][cnt];
     }
    }
    cout << dp[20][0] + dp[20][1] + dp[20][2] + dp[20][3] + dp[20][4] << ’\n’;
}

Решение на Python

dp = [[0] * 5 for _ in range(16 * 20 + 1)]
dp[10][0] = 1
for cnt in range(5):
    for x in range(16 * 20 + 1):
        if x + 1 <= 16 * 20:
            dp[x + 1][cnt] += dp[x][cnt]
        if x % 2 == 0 and cnt + 1 < 5:
            dp[x // 2][cnt + 1] += dp[x][cnt]
print(sum(dp[20]))

Решение с помощью рекурсии

from functools import lru_cache

@lru_cache(None)
def f(st, end, cnt):

    if (st > 20*16):
        return 0

    if (cnt > 4):
        return 0

    if (st == end):
        return 1 + f(st//2,end,cnt+1) + f(st+1, end, cnt)

    if (st%2 == 0):
        return f(st+1, end, cnt) + f(st//2, end, cnt+1)
    else:
        return f(st+1, end, cnt)


print(f(10,20,0))

Ответ: 469399

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

Задача 15#84011

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

1. Прибавь 8

2. Умножь на 3

3. Увеличь на разряд единиц

Первая из них увеличивает число на экране на 8, вторая увеличивает число на экране в 3 раза, третья увеличивает число на экране на значение разряда единиц (например число 12 увеличится на 2, а число 25 на 5). Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 4 результатом является число 174, если известно, что нельзя повторять команду, сделанную на предыдущем шаге.

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

# c - номер команды на предыдущем шаге
def f(a, b, c = 0):
    if a > b:
        return 0
    if a == b:
        return 1
    s = 0
    if c != 1:
        s += f(a + 8, b, 1)
    if c != 2:
        s += f(a * 3, b, 2)
    if c != 3:
        s += f(a + (a % 10), b, 3)
    return s

print(f(4, 174))

Ответ: 58

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

Задача 16#84013

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

1. Увеличь на разряд единиц

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

3. Умножь на разряд единиц

4. Умножь на разряд десятков

5. Прибавь 1

Первая и третья команды используют значение разряда единиц числа (например у 13 это 3, а у 28 - 8), а вторая и четвертая команды используют значение разряда десятков числа (например у 81 это 8, а у 35 это 3). Причём не разрешается выполнять команду, если после неё число на экране не изменится, либо превратится в 0. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 25 результатом является число 111, если известно, что нельзя повторять команду, сделанную два шага назад (например программа 112 допустима, а 121 - нет)?

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

from functools import lru_cache

# c1 - номер команды на предыдущем шаге
# с2 - номер команды на ПРЕДпредыдущем шаге

@lru_cache(None)
def f(a, b, c1 = 0, c2 = 0):
    if a > b:
        return 0
    if a == b:
        return 1
    s = 0
    x = a % 10  # Число единиц
    y = a // 10 % 10  # Число десятков

    if c2 != 1 and x != 0:
        s += f(a + x, b, 1, c1)

    if c2 != 2 and y != 0:
        s += f(a + y, b, 2, c1)

    if c2 != 3 and x != 0 and x != 1:
        s += f(a * x, b, 3, c1)

    if c2 != 4 and y != 0 and y != 1:
        s += f(a * y, b, 4, c1)

    if c2 != 5:
        s += f(a + 1, b, 5, c1)

    return s


print(f(25, 111))

Ответ: 3548990

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

Задача 17#84019

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

1. Увеличь на 4

2. Умножь на 2

3. Умножь на 3

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

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

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

Программное решение:

# c - номер команды на предыдущем шаге
# r - флаг наличия в траектории 6

def f(a, b, c = 0, r = False):
    if a > b or a == 18:
        return 0
    if a == b and r:
        return 1
    if a == 6:
        r = True

    s = f(a * 2, b, 2, r)
    if c != 1:
        s += f(a * 3, b, 3, r)
    if c != 2:
        s += f(a + 4, b, 1, r)
    return s

print(f(2, 296))

Ответ: 48

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

Задача 18#84021

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

1. Увеличь на 1

2. Увеличь на 3

3. Умножь на 4

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 824, при этом траектория вычислений содержит числa 21 и 68, причём можно использовать только ту команду, чей номер отличается на 1 от номера команды, выполненной на предыдущем шаге?

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

Программное решение:

# c — номер команды на предыдущем шаге
# r1 — флаг наличия в траектории 21
# r2 — флаг наличия в траектории 68

def f(a, b, c = 0, r1 = False, r2 = False):
    if a > b:
        return 0
    if a == b and r1 and r2:
        return 1
    if a == 21:
        r1 = True
    if a == 68:
        r2 = True

    if c == 1 or c == 3:
        return f(a + 3, b, 2, r1, r2)
    if c == 2:
        return f(a + 1, b, 1, r1, r2) + f(a * 4, b, 3, r1, r2)

    return f(a + 1, b, 1, r1, r2) + f(a + 3, b, 2, r1, r2) + f(a * 4, b, 3, r1, r2)

print(f(1, 824))

Ответ: 36

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

Задача 19#84023

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

1. Увеличь на 1

2. Умножь на 2

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

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

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

Программное решение:

# c1 - количество совершенных команд 1
# с2 - количество совершенных команд 2

def f(a, b, c1 = 0, c2 = 0):
    if a > b:
        return 0
    if a == b:
        return 1
    else:
        s = 0
        if c1 < 3:
            s += f(a + 1, b, c1 + 1, 0)
        if c2 < 3:
            s += f(a * 2, b, 0, c2 + 1)
    return s

print(f(5, 299))

Ответ: 26

23.08 Прочие прототипы