Тема 23. Оператор присваивания и ветвления

23.05 Количество программ из A в B смешанное

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела оператор присваивания и ветвления

Решаем задачи

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

Задача 1#6018

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

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

Прибавить 4
Прибавить 5
Умножить на 2

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

Сколько существует программ, для которых при исходном числе $3$ результатом является число $23$ и при этом траектория вычислений содержит число $11$ , но не содержит число $13$ и $18$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $7$ траектория будет состоять из чисел $11$ , $16$ , $32$ .

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

Решение №1

a = [0] * 24
a[3] = 1
for i in range(4, 24):
    a[i] = a[i - 4] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    if i == 11:
        for j in range(i):
            a[j] = 0
    if i == 13 or i == 18:
        a[i] = 0
print(a[23])

Решение №2

Составим фомулы для решения этой задачи:

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

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

Заметим, что число 3 мы получаем одним способом — пустой программой. Числа 4, 5 мы получить не можем данными командами. Заполним таблицу:

|--|--|--|--|--|--|--|----|---|---|---|---|----|---|---|---|---|----|---|---|---| |3-|4-|5-|6-|7-|8-|9-|10--|11-|12-|13-|14-|15--|16-|17-|18-|19-|-20-|21-|22-|23-| -1--0--0--1--1--1--0---1---2---0----0---0---2---2---0----0---2---4---2---2----2--

Ответ: 2

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#6069

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

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

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

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

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

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

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

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

$R(n ) = R (n − 1) + R (n − 2)$

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

|--|--|--|--|--|--|---| |1-|2-|3-|4-|5-|6-|-7-| -1--1--2--3--5--8--13--

По условию сказано, что траектория должна содержать число 8, значит $R (9) = 21$ , так как число 9 можем получить только первой командой.

Продолжим заполнять таблицу:

|1-|2-|3-|4-|5-|6-|-7--|8--|9--|10-|11-|-12--|13--| |--|--|--|--|--|--|----|---|---|---|---|-----|----| -1--1--2--3--5--8--13---21--21--42--63---105--168--

В условии сказано, что траектория не содержит число 14. Значит $R (14 ) = 0$ .

Заполним таблицу до конца:

|--|---|--|--|--|--|---|---|----|---|---|----|-----|---|----|-----|----|----|-----| |1-|2--|3-|4-|5-|6-|-7-|-8-|-9--|10-|11-|-12-|-13--|14-|-15-|-16--|17--|-18-|-19--| -1--1---2--3--5--8--13--21--21---42--63--105--168---0---168--168---336--504--840--|

Отсюда получаем ответ — 840.

Ответ: 840

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

Задача 3#6070

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 32 и при этом траектория вычислений содержит числа 13 и 25, но не содержит 28 и 31? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 1423 при сиходном числе 5 траектория будет состоять из чисел 6, 12, 15, 20.

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

Составим формулы для решения этой задачи:

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

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

Заполним таблицу:

|--|--|--|--|--|---|----|---|---|---|-----|----|----| |1-|2-|3-|4-|5-|-6-|-7--|8--|9--|10-|-11--|12--|-13-| -1--2--2--5--7--12--19---33--50--83--128---209--325--

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

|----|-----|----|----|-----|-----|------|-----|------|-----|-------|------|-------| |-13-|-14--|15--|-16-|-17--|-18--|-19---|-20--|-21---|-22--|--23---|-24---|--25---| -325--325---325--650--975---1625--2600---3900--6175---9750--15275---24050--37700--|

Аналогично траектория должна проходить через число 25. Заполним таблицу до конца, учитывая, что траектория не должна проходить через числа 28 и 31. Значит $R (28) = 0$ и $R (31) = 0$ .

|-------|-------|------|---|-------|--------|---|------| |--25---|--26---|-27---|28-|--29---|--30----|31-|--32--| -37700---37700---37700---0--37700---113100---0---75400--

Ответ: 75400

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

Задача 4#6767

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

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

Прибавить 1,

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

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 32 и при этом траектория вычислений содержит число 17, но не содержит числа 11 и 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 16, 48.

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

Составим формулы для решения этой задачи:

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

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

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

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

Заполним таблицу по данным формулам и со всеми условиями траектории.

|--|--|--|--|--|----|---|---|---|---|----|---|---|---|----|---|---| |1 |2 |3 |4 |5 | 6 |7 |8 | 9 |10 | 11 |12 |13 |14 |15 |16 |17 | |1-|2-|3-|5-|5-|10--|10-|15-|18-|23-|-0--|15-|15-|-0-|-5--|20-|20-| -------------------------------------------------------------------

Так как траектория должна проходить через число 17, то последующие числа мы можем получить только командой 1. Количество программ изменится только на $17 ⋅ 2 = 34$ . Отсюда следует, что ответ 20.

Ответ: 20

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

Задача 5#6867

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

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

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

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

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

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

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

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

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

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

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

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

|--|--|--|--|--|--|--|----|---|---| |2-|3-|4-|5-|6-|7-|8-|-9--|10-|11-| |1 |1 |1 |2 |4 |5 |7 | 12 |17 |24 | -----------------------------------

По условию сказано, что траектория должна содержать число 12. Значит $R(13) = 37$ , так как число 13 можно получить только командой 1.

Продолжим заполнять таблицу:

|---|----|---|---|---|-----|----|----|-----|----|----|------|-----|------|-----|------| |11-|-12-|13-|14-|15-|-16--|17--|-18-|-19--|20--|-21-|--22--|-23--|-24---|-25--|-26---| -24---37--37--37--74--111---148--222--333---481--703--1036---1517--2220---3256--4773--|

По услолвию сказано, что траектория не должна содержать число 27. Значит $R (27) = 0$ .

Заполним таблицу до конца:

|-----|---|------|-----|------|------|-------|------| |-26--|27-|-28---|-29--|-30---|-31---|--32---|-33---| -4773---0--3256---8029--8029---11285--19314---27343--

Отсюда получаме ответ — 27343

Ответ: 27343

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

Задача 6#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

Курсы

Всё необходимое для достижения цели

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

Задача 7#6869

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

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

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

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

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

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

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

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

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

Составим формулы:

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

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

Заметим, что количество программ будет меняться только на числах кратных 5. Заполним таблицу по данным формулам, учитывая условия траектории:

|---|---|----|---|---|---|---|----|---|---|---|----|---|---|---|---|-----|----| |15-|20-|25--|30-|35-|40-|45-|50--|55-|60-|65-|70--|75-|80-|85-|90-|-95--|100-| |1 | 1 | 0 |2 |2 | 0 | 2 | 4 |2 |4 | 6 |10 |16 |26 |42 |68 |110 |180 | -------------------------------------------------------------------------------

Лютик точно будет спасён!

Ответ: 180

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

Задача 8#11535

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

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

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

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

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

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

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

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

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

a = [0]*17
a[1] = 1
for i in range(2, 17):
    a[i] = a[i-1]
    if i > 5:
        a[i] += a[i-5]
    if i % 2 == 0:
        a[i] += a[i//2]
    if i == 10:
        a[i] = 0
    if i == 8:
        for j in range(8):
            a[j] = 0
print(a[16])

Ответ: 45

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

Задача 9#11542

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

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

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

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

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

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

a = [0]*51
a[1] = 1
for i in range(2, 51):
    a[i] = a[i-1]
    if i % 2 == 0:
        a[i] += a[i//2]
    if i % 3 == 0:
        a[i] += a[i//3]
    if i == 14:
        for j in range(14):
            a[j] = 0
    if i == 16:
        a[i] = 0
print(a[50])

Ответ: 192

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

Задача 10#25594

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

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

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

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

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

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

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

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

Ответ: 120

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

Задача 11#25942

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

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

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

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

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

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

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

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

a = [0]*21
a[3] = 1
for i in range(4, 21):
    a[i] = a[i-1]+a[i-3]
    if i % 4 == 0:
        a[i] += a[i//4]
    if i == 12:
        for j in range(i):
            a[j] = 0
    if i == 7:
        a[i] = 0
print(a[20])

Ответ: 104

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#26183

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

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

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

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

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

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

Ответ дайте в шестеричной системе счисления

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

def perevod(n, a):
    s = ’’
    while n != 0:
        s = str(n % a) + s
        n //= a
    return s


a = [0]*46
a[3] = 1
for i in range(4, 46):
    a[i] = a[i-1]
    if i % 2 == 0:
        a[i] += a[i//2]
    if i == 15:
        a[i] = 0
    if i == 10:
        for j in range(i):
            a[j] = 0
print(perevod(a[45], 6))

Ответ: 100

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

Задача 13#29370

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

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

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

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

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

def f(s, fi, flag):
    if s > fi:
        return 0
    if s == 99:
        return 0
    if s == 50:
        flag = True
    if s == fi and flag:
        return 1
    return f(s + 2, fi, flag) + f(s * 3, fi, flag)
print(f(10, 100, False))

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

a = [0] * 101
a[10] = 1
for i in range(11, 101):
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0)
    if i == 99:
        a[i] = 0
    if i == 50:
        for j in range(i):
            a[j] = 0
print(a[100])

Ответ: 5

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

Задача 14#30475

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

Прибавить $3$
Умножить на $2$
Возвести в третью степень

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $6$ траектория будет состоять из чисел $9,18,5832$ .

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

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

def f(st, fn, flag, flag_number, exit_number):
    if st == fn and flag:
        return 1
    if st > fn or st == exit_number:
        return 0
    if st == flag_number: # поднимаем флаг, если дошли до требуемого значения
        flag = True
    x = f(st + 3, fn, flag, flag_number, exit_number)
    y = f(st * 2, fn, flag, flag_number, exit_number)
    z = f(st ** 3, fn, flag, flag_number, exit_number)
    return x + y + z
print(f(3, 96, False, 12, 25))

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

a = [0] * (96 ** 3 + 1)
a[3] = 1
for i in range(3, 96):
    if i == 12:
        b = a[i]
        a = [0] * (96 ** 3 + 1)
        a[i] = b
    if i != 25:
        a[i + 3] += a[i]
        a[i * 2] += a[i]
        a[i ** 3] += a[i]
print(a[96])

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

a = [0] * 97
a[3] = 1
for i in range(4, 97):
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0)
    x = int(i ** (1 / 3))
    if x ** 3 == i:
        a[i] += a[x]
    if i == 12:
        for j in range(i):
            a[j] = 0
    if i == 25:
        a[i] = 0
print(a[96])

Ответ: 160

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

Задача 15#30479

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

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

2. Если число кратно $8$ , прибавить к нему это же число, умноженное на $0.75$

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

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 14, 28.

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

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

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

def f(st, fn, flag, flag_number, count, end_count):
    if st == fn and count == end_count and flag:
        return 1
    if st > fn or count > end_count:
        return 0
    if st == flag_number:
        flag = True
    x = f(st + 1, fn, flag, flag_number, count + 1, end_count)
    y = f(st * 2, fn, flag, flag_number, count + 1, end_count)
    z = f(st + st * 0.75, fn, flag, flag_number, count + 1, end_count) * \
(st % 8 == 0)
    return x + y + z
print(f(3, 50, False, 15, 0, 20))

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

ans = []
ans.append((3, 0))
for operations in range(20):
    can_get = []
    for i in ans:
        a, flag = i
        if a + 1 == 15:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        if a % 8 == 0:
            if int(a + a * 0.75) == 15:
                can_get.append((int(a + a * 0.75), 1))
            else:
                can_get.append((int(a + a * 0.75), flag))
        can_get.append((a * 2, flag))
    ans = can_get
otv = 0
for i in ans:
    a, flag = i
    if (a == 50) and (flag):
        otv += 1
print(otv)

Ответ: 9

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

Задача 16#30480

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

1. Прибавить 2, если число кратно 3

2. Прибавить 3, если число кратно 2

3. Прибавить 1, если число не кратно ни 2, ни 3

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 3 траектория будет состоять из чисел 5, 6, 9.

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

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

def f(st, fn, exit_number, count, end_count):
    if st == fn and count == end_count:
        return 1
    if st > fn or count > end_count or st == exit_number:
        return 0
    x = f(st + 2, fn, exit_number, count + 1, end_count) * (st % 3 == 0)
    y = f(st + 3, fn, exit_number, count + 1, end_count) * (st % 2 == 0)
    z = f(st + 1, fn, exit_number, count + 1, end_count) * (st % 2 != 0
                                                            and st % 3 != 0)
    return x + y + z
print(f(3, 27, 22, 0, 12))

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

ans = []
ans.append(3)
for operations in range(12):
    can_get = []
    for i in ans:
        if i == 22:
            continue
        if i % 3 == 0:
            can_get.append(i + 2)
        if i % 2 == 0:
            can_get.append(i + 3)
        if (i % 2 != 0) and (i % 3 != 0):
            can_get.append(i + 1)
    ans = can_get
print(ans.count(27))

Ответ: 8

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#30481

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

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

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

3. Прибавить само число

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

Сколько существует программ, для которых при исходном числe 1 результатом является число 28, при этом программа содержит 9 команд, а траектория обязательно не проходит через число 11 и проходит через 13?

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

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

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

def f(st, fn, flag, flag_number, exit_number, count, end_count):
    if st == fn and count == end_count and flag:
        return 1
    if st > fn or count > end_count or st == exit_number:
        return 0
    if st == flag_number:
        flag = True
    x = f(st + 1, fn, flag, flag_number, exit_number, count + 1, end_count)
    y = f(st + 3, fn, flag, flag_number, exit_number, count + 1, end_count)
    z = f(st * 2, fn, flag, flag_number, exit_number, count + 1, end_count)
    return x + y + z
print(f(1, 28, False, 13, 11, 0, 9))

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

ans = []
ans.append((1, 0))
for operations in range(9):
    can_get = []
    for i in ans:
        a, flag = i
        if a == 11:
            continue
        if a + 3 == 13:
            can_get.append((a + 3, 1))
        else:
            can_get.append((a + 3, flag))
        if a + 1 == 13:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        if 2 * a == 13:
            can_get.append((2 * a, 1))
        else:
            can_get.append((2 * a, flag))
    ans = can_get
otv = 0
for i in ans:
    a, flag = i
    if (a == 28) and (flag):
        otv += 1
print(otv)

Ответ: 63

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

Задача 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#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

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

Задача 20#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

Предыдущий раздел

Следующий раздел