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

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

Задача 1#6055

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

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

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

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

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

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

Решение 1

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

Решение 2

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

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

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

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

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

По условию траектория должна проходить через число 11, значит $R (12) = 6$ , так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:

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

Аналагично $R(19) = 24$ , так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:

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

Отсюда получаем ответ: 72.

Ответ: 72

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

Задача 2#6071

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

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

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

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

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

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

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

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

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

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

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

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

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

По условию сказано, что траектория должна проходить через число 10, значит $R (11) = 30$ , так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:

|--|--|--|--|--|--|----|---|---|---|----|---|---|----|-----|----| |2-|3-|4-|5-|6-|7-|-8--|9--|10-|11-|12--|13-|14-|-15-|-16--|17--| |1 |1 |2 |3 |5 |7 | 12 |17 |27 |27 |27 |54 |81 |108 |162 |243 | -----------------------------------------------------------------

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

Ответ: 243

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

Задача 3#6838

Исполнитель РЫБИНСК преобразует число на экране.

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

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя РЫБИНСК — это последовательность команд.

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

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

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

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

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

|--|---|--|--|--|--|---|---|----| |1-|2--|3-|4-|5-|6-|-7-|-8-|-9--| -1--1---2--3--5--8--13--21--34--|

По формуле $R (10 ) = R(9) + R (8) = 55$ , но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно $R (10) = R (9) = 34$ .

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

|--|--|--|---|--|--|---|---|---|----|---|----|----|-----| |1-|2-|3-|4--|5-|6-|7--|-8-|-9-|10--|11-|12--|-13-|-14--| |1 |1 |2 |3 |5 |8 |13 |21 |34 |34 |68 |102 |170 | 272 | --------------------------------------------------------

Отсюда получаем искомое количество программ — 272.

Ответ: 272

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

Задача 4#6839

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|--|--|--|--|--|--|---|---|---|---|---|----|---|---|---|----|---|---|---|---|----|---|---|---|----|---| |3-|4-|5-|6-|7-|8-|-9-|10-|11-|12-|13-|14--|15-|16-|17-|18--|19-|20-|21-|22-|23--|24-|25-|26-|27--|28-| -1--0--1--1--1--2---3--3---5----6---0---6---6---6---12--12---0---12--12--12--24---24--36--48--60---84-|

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

Ответ: 84

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

Задача 5#6840

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 38 и при этом траектория содержит числа 14 и 29? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.

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

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

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

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

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

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

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

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

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

|14-|15-|16-|17-|-18-|19-|20-|-21-|-22--|23--|-24--|25--|26--|-27--|28--|-29--| |---|---|---|---|----|---|---|----|-----|----|-----|----|----|-----|----|-----| -36--0---36--36---36--72--72--108---144--180--252---324--432--576---756--1008--

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

|-----|---|------|-----|------|-----|------|-----|------|-----| |-29--|30-|--31--|-32--|--33--|-34--|-35---|-36--|-37---|-38--| |1008 | 0 | 1008 |1008 |1008 |2016 |2016 |3024 |4032 |5040 | ---------------------------------------------------------------

Отсюда получаем ответ: 5040.

Ответ: 5040

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

Задача 6#6841

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 27 и при этом траектория содержит числа 13 и 19 ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

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

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

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

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

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

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

Используя данные формулы, заполним таблицу до 13:

|2-|3-|4-|5-|6-|-7-|-8--|9--|10-|-11-|-12--|13--| |--|--|--|--|--|---|----|---|---|----|-----|----| -1--1--3--4--9--13---25--39--68--107---187--294--

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

|13--|-14-|-15--|16--|-17--|--18--|-19--| |----|----|-----|----|-----|------|-----| -294--294--588---882--1470--2352---3822--

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

|-----|------|-----|-------|-------|------|-------|------|--------| |-19--|--20--|-21--|--22---|--23---|-24---|--25---|-26---|---27---| -3822--3822---7644--11466---19110---30576--49686---80262--129948---

Отсюда получаем ответ – 129948.

Ответ: 129948

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

Задача 7#6866

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — $R(12) = R (11)$ . Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.

В итоге получаем ответ — 7

Ответ: 7

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

Задача 8#16521

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

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

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

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

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

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

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

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

Рекурсия:

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

print(f(1, 9) * f(9, 15))

Динамика:

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

Ответ: 234

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

Задача 9#16523

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

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

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

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

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

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

Рекурсия:

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

print(f(3, 8) * f(8, 18))

Динамика:

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

Ответ: 24

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

Задача 10#16524

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

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

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

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

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

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

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

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

Рекурсия:

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

print(f(3, 22) * f(22, 35))

Динамика:

a = [0] * 1000
a[3] = 1
for i in range(3, 22 + 1):
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]
for i in range(1000):
    if i != 22:
        a[i] = 0
for i in range(22, 35 + 1):
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]
print(a[35])

Ответ: 108

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

Задача 11#16525

Исполнитель СНЕГОВИК преобразует число, записанное на экране.

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

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

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

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

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

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

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

Рекурсия:

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

print(f(3, 11) * f(11, 27))

Динамика:

a = [0] * 1000
a[3] = 1
for i in range(3, 11+1):
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 4] += a[i]
for i in range(1000):
    if i != 11:
        a[i] = 0
for i in range(11,27+1):
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 4] += a[i]
print(a[27])

Ответ: 665

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

Задача 12#22657

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

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

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

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

Сколько существует программ, для которых при исходном числе $3$ результатом является число $35$ и при этом траектория содержит число $22$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $4$ , $8$ , $16$ .

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

Рекурсия:

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

print(f(3, 22) * f(22, 35))

Динамика:

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

Ответ: 108

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

Задача 13#22658

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

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

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

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

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

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

Решение №1

a = [0] * 27 * 4
a[3] = 1
for i in range(3, 27):
    if i == 11:
        for j in range(i + 1, 27 * 4):
            a[j] = 0
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 4] += a[i]
print(a[27])

Решение №2

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

Ответ: 665

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

Задача 14#24007

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

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

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

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

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

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

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

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

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

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

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

print(a[13])

Ответ: 120

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

Задача 15#24745

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

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

Первая команда увеличивает число на экране на $3$ , вторая увеличивает его в $2$ раза. Сколько существует программ, для которых при исходном числе $12$ результатом будет число $96$ , обязательно проходящее через число $30$ .

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

Рекурсия:

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

print(f(12, 30) * f(30, 96))

Динамика:

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

Ответ: 24

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

Задача 16#25621

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

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

2. Прибавь $5$ ;

3. Возведи в квадрат.

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

Программа для исполнителя ШКОЛКОВО это последовательность команд.

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

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

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

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

def f(start, finish):
    if start == finish:
        return 1
    if start > finish:
        return 0
    return f(start + 1, finish) + f(start + 5, finish) + f(start * start, finish)

print(f(2, 5) * f(5, 26))

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

a = [0] * 27
a[2] = 1
for i in range(3, 27):
    a[i] += a[i - 1] + a[i - 5]
    sq = int(i ** 0.5)
    if sq ** 2 == i:
        a[i] += a[sq]
    if i == 5:
        for j in range(1, 5):
            a[j] = 0
print(a[26])

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

a = [0] * 10000
a[2] = 1
for i in range(2, 26):
    if i == 5:
        for j in range(6, 27):
            a[j] = 0
    a[i + 1] += a[i]
    a[i + 5] += a[i]
    a[i * i] += a[i]
print(a[26])

Ответ: 372

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

Задача 17#25783

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

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

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

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

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

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

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

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

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

def f(s, fi, flag = False):
    if s == 9:
        flag = True
    if (s == fi) and (flag):
        return 1
    if s > fi:
        return 0
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)
print(f(3, 14))

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

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

Ответ: 112

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

Задача 18#30472

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

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

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

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

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

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

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

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

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

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

print(f(2, 10) * f(10, 30))

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

a = [0] * 31 * 3
a[2] = 1
for i in range(2, 30):
    if i == 10:
        b = a[i]
        a = [0] * 31 * 3
        a[i] = b # удалили все значения кроме ячейки a[15]
    a[i + 3] += a[i]
    a[i * 2] += a[i]
    a[i + 1] += a[i]
print(a[30])

Ответ: 36126

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

Задача 19#33618

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

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

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

2. Вычесть $3$

3. Взять целую часть от деления на $3$ .

Первая команда уменьшает число на экране на $1$ , вторая уменьшает число на экране на $3$ , третья заменяет число на экране на целую часть от деления на $3$ .

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

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

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

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

Рекурсия:

def f(x, y):
    if x == y:
        return 1
    if x < y:
        return 0
    else:
        return f(x - 1, y) + f(x - 3, y) + f(x // 3, y)

print(f(38, 14) * f(14, 1))

Ответ: 1379664

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

Задача 20#43111

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

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

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

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

3. Разделить на $5$ , если кратно $5$ .

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

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

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

Программа:

def f(x, y):
    if x == y:
        return 1
    if x < y:
        return 0

    if x % 5 == 0:
        return f(x - 5, y) + f(x - 2, y) + f(x // 5, y)
    else:
        return f(x - 5, y) + f(x - 2, y)

print(f(49, 13) *f(13, 1))

Ответ: 3425

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