Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика БУ
Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

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

23.04 Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

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

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

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

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

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

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

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

Задача 1#49387

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

1. прибавь 1

2. прибавь 5

3. умножь на 2

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

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

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

def f(x, y):
    if x == y:
        return 1
    if x > y or x==10:
        return 0
    return f(x + 1, y) + f(x + 5, y) + f(2 * x , y)
print(f(2, 16))

Ответ: 40

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

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

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

Задача 2#6054

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

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

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

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

Сколько существует программ, для которых при исходном числе $256$ результатом является число $273$ и при этом траектория вычислений не содержит числа $262$ и $270$ ? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $7$ траектория будет состоять из чисел $10$ , $14$ , $17$ .

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

Решение 1

a = [0] * 274
a[256] = 1
for i in range(257, 274):
    a[i] = a[i - 3] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    if i == 262 or i == 270:
        a[i] = 0
print(a[273])

Решение 2

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

Заметим, что $256 ⋅ 2 = 512$ — это больше числа, которое нам нужно найти, значит 3-я команда нам не понадобится. Составим уравнение:

$R(n ) = R (n − 3) + R (n − 4)$

Составим таблицу по данному уравнению:

|----|-----|----|----|-----|----| |256-|257--|258-|259-|260--|261-| --1----0-----0----1----1-----0---

Так как траектория не должна содержать число 262, то $R (262) = 0$ . Продолжим заполнение таблицы:

|261-|262--|263-|264-|265--|266-|267-|268--|269-| |----|-----|----|----|-----|----|----|-----|----| --0----0-----2----1----0-----2----3----1-----2---

Аналогично $R(270 ) = 0$ .

|----|----|-----|----|----| |269-|270-|271--|272-|273-| | 2 | 0 | 4 | 3 | 2 | ---------------------------

Отсюда ответ — 2.

Ответ: 2

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

Задача 3#6068

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

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

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

2. умножить на 2,

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

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

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

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

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

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

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

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

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

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

|1-|2-|3-|4-|5-|-6--|7--|8--| |--|--|--|--|--|----|---|---| -1--2--3--5--5--10---10--15--

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

|--|--|--|--|--|----|---|---|--|---|---|----|---|---|---|----|---|---|---|---|----|---|---| |1-|2-|3-|4-|5-|-6--|7--|8--|9-|10-|11-|-12-|13-|14-|15-|16--|17-|18-|19-|20-|21--|22-|23-| -1--2--3--5--5--10---10--15--0---5---5---20--20--30--35--50---50--60--60--70--80---85--85--

Аналогично $R (24) = 0$ . Продолжим заполнять таблицу:

|---|---|----|---|---|---|----|---|---| |23-|24-|25--|26-|27-|28-|29--|30-|31-| -85---0---0---20--20--50--50---90--90--

Аналогично $R (32) = 0$ . Заполним таблицу до конца:

|----|---|---|---|----|----|----|-----| |31--|32-|33-|34-|35--|36--|37--|-38--| |90 |0 |5 |55 |55 |135 |135 |195 | --------------------------------------

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

Ответ: 195

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

Задача 4#6833

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя САЛФЕТОЧКА — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений не содержит число 8? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 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 (8 ) = 0$ .

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

|--|--|--|--|--|--|----|--|---|---|---|----|---|----| |1 |2 |3 |4 |5 |6 | 7 |8 |9 |10 |11 |12 |13 |14 | |--|--|--|--|--|--|----|--|---|---|---|----|---|----| -1--1--2--3--5--8--13---0--13--13--26--39---65--104--

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

Ответ: 104

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

Задача 5#6834

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

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

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

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

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

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

Решение 1

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

Решение 2

a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14:
        a[i] = 0
    a[i + 1] += a[i]
    a[i * 2] += a[i]
print(a[19])

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

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

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

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

Так как по условию сказано, что траектория не должна проходить через число 14, значит мы никак не можем его получить, что означает $R(14) = 0$ .

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

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

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

Ответ: 20

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

Задача 6#6835

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

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

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

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

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

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

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

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

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

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

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

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

|--|--|--|--|--|----|---|---|---|---|----|----|----|-----|----| |1-|2-|3-|4-|5-|-6--|7--|8--|-9-|10-|-11-|12--|-13-|-14--|15--| |1 |2 |2 |5 |7 |11 |16 |28 |39 |62 | 90 |140 |202 |308 |448 | ---------------------------------------------------------------

Так как по условию сказано, что траектория не должна проходить через число 16, значит мы никак не можем его получить, что означает $R(16) = 0$ .

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

|--|--|--|--|--|----|---|---|---|---|----|----|----|-----|----|---|-----|----|----|------|-----|------| |1-|2-|3-|4-|5-|-6--|7--|8--|-9-|10-|11--|12--|-13-|-14--|15--|16-|-17--|18--|-19-|-20---|-21--|-22---| -1--2--2--5--7--11---16--28--39--62--90---140--202--308---448---0--308---795--795--1165---1960--2845--|

Аналогично $R (23) = 0$ .

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

|-22--|23-|--24--|-25--|-26---|-27--| |-----|---|------|-----|------|-----| -2845---0--2100---4945--5147---7247--

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

Ответ: 7247

Курсы

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

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

Задача 7#6836

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

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

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

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

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

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

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

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

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

$R(n ) = R (n − 2) + R (n − 3) + R (n − 5)$

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

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

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

|--|--|--|--|---|--|--|--|--|---|---|----|---|---|---|---|----|---| |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 |14 |15 |16 |17 |18 | |1-|0-|1-|1-|1--|3-|2-|5-|6-|-8-|14-|16--|0--|36-|24-|50-|76--|74-| ------------------------------------------------------------------|

Аналогично $R (19) = 0$ . Заполним таблицу до конца:

|1-|2-|3-|4-|5-|6-|7--|8-|9-|10-|11-|12-|13--|14-|15-|16-|17--|18-|19-|-20-|-21--|22--|-23-|-24--|25--| |--|--|--|--|--|--|---|--|--|---|---|---|----|---|---|---|----|---|---|----|-----|----|----|-----|----| -1--0--1--1--1--3--2---5--6--8---14--16---0---36--24--50--76---74--0---174--124---250--372--374---796--

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

Ответ: 796

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

Задача 8#6837

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 3 результатом является число 45 и при этом траектория вычисления не содержит числа 5, 17 и 35? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 1314 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17, 51.

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

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

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

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

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

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

Сразу заметим, что по условию задачи траектория не должна содержать числа 5, 17 и 35. Значит $R (5) = 0$ , $R (17 ) = 0$ и $R (35 ) = 0$ .

Составим таблицу по данным формулам:

|--|--|--|--|--|---|--|---|---|---|----|---|---|----|----|---|----|----|-----|----|----|------| |3-|4-|5-|6-|7-|-8-|9-|10-|11-|12-|13--|14-|15-|-16-|17--|18-|19--|-20-|-21--|22--|-23-|--24--| -1--1--0--2--3---4--7--10--14--24--34---51--75--113---0---84--197--207--294---505--712---1034--

|-----|------|-----|------|-----|------|------|-------|------|-------|------|----|------|-------|------|--------| | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | |-----|------|-----|------|-----|------|------|-------|------|-------|------|----|------|-------|------|--------| -1034--1539---2285--3326---4916--7201---10612--15528---22842--33468---48996---0---33576--82572---82769--116379---

|--------|--------|-------|--------|--------|---------| |---40---|--41----|--42---|---43---|--44----|---45----| -199158---281927---398651--597809---880241---1278967--|

Получаем ответ – 1278967.

Ответ: 1278967

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

Задача 9#11532

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

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

$2$ . Сделать нечётное

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

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

a = [0]*28
a[1] = 1
for i in range(2,28):
    a[i] = a[i-1]
    if i%2==1:
        a[i] += a[i//2]
    if i==26:
        a[i]=0
print(a[27])

Ответ: 13

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

Задача 10#16526

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

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

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

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

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

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

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

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

num = [0]*73
num[33] = 1
for i in range(34, 73):
num[i] = ((num[i-1] + num[i-4]) + num[i//2] * (i % 2 == 0)) * (i != 30)
print(num[72])

Ответ: 157430

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

Задача 11#22659

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 33 результатом является число 72 и при этом траектория не содержит число 56? Траектория вычислений программы $−$ это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 1 траектория будет состоять из чисел 2, 6, 12.

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

a = [0] * 10000
a[33] = 1
for i in range(33, 73):
    a[56] = 0
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]
print(a[72])

Ответ: 71265

Интенсивы

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

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

Задача 12#25108

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

Прибавить $1$ ;
Сделай нечётное.

Выполняя первую команду, исполнитель увеличивает число на $1$ , а выполняя вторую — из числа $k$ получает число $2k + 1$ .

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

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

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

def f(s, fi):
    if s > fi:
        return 0
    if s == 21:
        return 0
    if s == fi:
        return 1
    return f(s + 1, fi) + f(s * 2 + 1, fi)
print(f(1, 25))

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

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

Ответ: 20

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

Задача 13#25567

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

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

Первая команда увеличивает число, записанное на экране, на $1$ , вторая — на $3$ , третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя ЭМИ — это последовательность команд. Сколько существует программ, для которых при исходном числе $3$ результатом является число $45$ и при этом траектория вычисления не содержит числа $5,17$ и $35$ ?

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

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

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

Ответ: 1278967

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

Задача 14#25915

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

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

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

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

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

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

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

def f(start, finish):
    if start == finish:
        return 1
    if start > finish or start == 8:
        return 0
    return f(start + 1, finish) + f(start + 2, finish) + f(start * 2, finish)
print(f(3, 13))

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

a = [0] * 14
a[3] = 1
for i in range(4, 14):
    if i == 8:
        continue
    a[i] += a[i - 1]
    a[i] += a[i - 2]
    if i % 2 == 0:
        a[i] += a[i // 2]
print(a[13])

Ответ: 40

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

Задача 15#26985

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

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

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

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

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

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

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

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

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

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

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

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


print(f(2, 20))

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

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

Ответ: 304

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

Задача 16#30473

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

Прибавить $2$
Умножить на $3$
Прибавить остаток от деления на $2$ и прибавить $2$

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

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

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

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

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

def f(st, fn, exit_number):
    if st == fn:
        return 1
    if st > fn or st == exit_number:
        return 0
    x = f(st + 2, fn, exit_number)
    y = f(st * 3, fn, exit_number)
    z = f(st + st % 2 + 2, fn, exit_number)
    return x + y + z
print(f(1, 15, 13))

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

a = [0] * 16 * 3
a[1] = 1
for i in range(1, 15):
    if i != 13:
        a[i + 2] += a[i]
        a[i * 3] += a[i]
        a[i + i % 2 + 2] += a[i]
print(a[15])

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

a = [0] * 16
a[1] = 1
# 2 -> 2 + 0 + 2 = 4
# 1 -> 1 + 1 + 2 = 4
for i in range(2, 16):
    a[13] = 0
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0) + (a[i - 2] + a[i - 2 - 1]) * (i % 2 == 0)
print(a[15])

Ответ: 2

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

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

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

Задача 17#43112

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

1. Вычесть $1$ ;

2. Поделить на $3$ нацело.

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $12$ при исходном числе $11$ траектория будет состоять из чисел $10,3$ .

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

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

Ответ: 189

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

Задача 18#58103

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

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

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

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

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

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

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

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

Ответ: 76

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

Задача 19#58501

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

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

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

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

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

a = [0] * 100
a[4] = 1
for i in range(5, 48):
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0)
    a[28] = 0
print(a[47])

Ответ: 11

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

Задача 20#60489

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

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

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

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

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

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

print(f(5, 31))

Ответ: 12

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

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