ЕГЭ-13. Динамическое программирование

(Е. Джобс) У исполнителя Калькулятор имеются две команды, которым присвоены номера:

1. Прибавь 3

2. Умножь на 2

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 2. Сколько существует программ, для которых при исходном числе 3 результатом является число 105, и при этом траектория вычислений содержит число 30?

(ЕГЭ-2023) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Вычесть 1

2. Вычесть 3

3. Найти целую часть от деления на 2

Выполняя первую из них, исполнитель уменьшает число на экране на 1, выполняя вторую – уменьшает на 3, выполняя третью – делит на 2 нацело, отбрасывая остаток. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, и при этом траектория вычислений содержит число 10 и не содержит числа 7?

(ЕГЭ-2023) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Вычесть 1

2. Вычесть 2

3. Найти целую часть от деления на 3

Выполняя первую из них, исполнитель уменьшает число на экране на 1, выполняя вторую – уменьшает на 2, выполняя третью – делит на 3 нацело, отбрасывая остаток. Сколько существует программ, для которых при исходном числе 19 результатом является число 3, и при этом траектория вычислений не содержит чисел 9 и 16?

(ЕГЭ-2023) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 2

2. Прибавь 3

3. Умножь на 2

Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – увеличивает на 3, выполняя третью – умножает на 2. Сколько существует программ, для которых при исходном числе 3 результатом является число 25, и при этом траектория вычислений содержит число 10 и не содержит число 17?

(Е. Джобс) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2, выполняя третью – умножает на 3. Сколько существует программ, для которых при исходном числе 6 результатом является число 25, и при этом траектория вычислений содержит либо число 15, либо 21, но не оба сразу?

(Е. Джобс) У исполнителя Калькулятор имеются две команды, которым присвоены номера:

1. Прибавь 2

2. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3. Сколько различных чисел можно получить с помощью программы из четырех команд из числа 1?

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

1. Вычти 5

2. Прибавь 2

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

Выполняя первую из них, исполнитель уменьшает число на экране на 5, выполняя вторую –увеличивает на 2, выполняя третью – возводит число в квадрат. Исполнитель работает только с натуральными числами. Программой для исполнителя называется последовательность команд. Сколько существует программ, состоящих ровно из 7 команд, для которых при исходном числе 3 результатом является число 28?

(Е. Джобс) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Вычти 2

2. Раздели нацело на 2

3. Раздели нацело на 3

Выполняя первую из них, исполнитель уменьшает число на экране на 2, выполняя вторую – делит нацело на 2, выполняя третью – делит нацело на 3. Сколько существует программ, для которых при исходном числе 40 результатом является число 2, и при этом траектория вычислений не содержит число 22?

(А. Богданов) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 3

3. Прибавь 7

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 3, выполняя третью – увеличивает на 7. Рассматриваются только такие программы, при выполнении которых все пары соседних чисел в траектории должны быть взаимно простыми, т. е. не должны иметь общих делителей, кроме 1. Например, из числа 24 командой 2 (+3) нельзя перейти в число 27, потому как оба эти числа делятся на 3. А из числа 25 можно перейти в 28. Для этих чисел нет общих простых делителей, т.е. числа взаимно простые. Сколько существует подходящих программ, для которых при исходном числе 13 результатом является число 31?

(М. Шагитов) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 3

2. Прибавь 5

3. Умножь на 2

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – увеличивает на 5, выполняя третью – умножает число на 2.

Сколько существует программ, которые преобразуют число 1 в число 10000 и при этом траектория вычислений программы содержит число 3000 или 5000, но не оба эти числа одновременно? В ответе запишите последние 6 цифр этого числа.

(М. Шагитов) У исполнителя Калькулятор имеются три команды, которым присвоены номера:

1. Прибавь 3

2. Прибавь 5

3. Умножь на 2

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – увеличивает на 5, выполняя третью – умножает число на 2.

Укажите количество программ, которые преобразуют число 4 в число 68 и при этом траектория вычислений программы содержит число 16 или 32, но не оба эти числа одновременно.

(А. Богданов) У исполнителя Цифрень имеются две команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2.

Определим цифровой корень числа как сумму цифр числа, которая вычисляется рекурсивно до тех пор, пока не останется одна цифра. Например, для числа 1993 цифровой корень вычисляется как 1+9+9+3 = 22 => 2+2 = 4.

Сколько существует различных программ, преобразующих число 12 в число 37 и не содержащих команд, в которых цифровой корень исходного числа равен младшей цифре числа-результата? Например, к числу 18 (цифровой корень 9) можно применить команду 2, так что получим 20 (9 0). Но к числу 20 (цифровой корень 2) команду 2 применить нельзя, так как последняя цифра результата 22, равная 2, совпадает с цифровым корнем исходного числа.

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 3, выполняя третью – умножает на 3. Сколько существует различных программ, преобразующих число 3 в число 95 и содержащих не более шести команд 1, при выполнении которых траектория вычислений содержит число 37 и не содержит чисел 20 и 58?

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2, выполняя третью – умножает на 3. Сколько существует различных программ, преобразующих число 1 в число 43 и содержащих не более трёх команд 1, при выполнении которых траектория вычислений содержит число 25 и не содержит чисел 10 и 38?

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 3, выполняя третью – умножает на 2. Сколько существует различных программ, преобразующих число 2 в число 40 и содержащих не более пяти команд 1, при выполнении которых траектория вычислений содержит число 18 и не содержит чисел 11 и 35?

(А. Богданов) У исполнителя Прайм имеются три команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2, выполняя третью – умножает на 3. Сколько существует программ, для которых при исходном числе 8 результатом является число 32 и при этом траектория вычислений содержит число 16 и не содержит простых чисел?

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

4. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 3, выполняя третью – умножает на 2, выполняя четвертую – умножает на 3. Сколько существует различных программ, преобразующих число 1 в число 9999, которые не содержат двух подряд идущих команд сложения и двух подряд идущих команд умножения?

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

4. Умножь на 3

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2, выполняя третью – умножает на 2, выполняя четвертую – умножает на 3. Сколько существует различных программ, преобразующих число 1 в число 55555, которые не содержат двух подряд идущих команд сложения и двух подряд идущих команд умножения?

(А. Игнатюк) У исполнителя Д-503 имеются три команды, которым присвоены номера:

1. Прибавь 3

2. Умножь на А

3. Прибавь С

где A и C – натуральные числа, не превышающие 100. Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на А, выполняя третью – увеличивает на C. Известно, что при выполнении программы 1323123 исполнитель преобразует число 5 в число 329. Определите значения А и С, запишите в ответе их сумму.

(PRO100 ЕГЭ) У исполнителя Калькулятор имеются четыре команды, которым присвоены номера:

1. Прибавь 1

2. Прибавь 2

3. Прибавь 3

4. Умножь на 4

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 2, выполняя третью – увеличивает на 3, выполняя четвёртую – умножает на 4. Сколько существует программ, для которых при исходном числе 38 результатом является число 68, при этом траектория вычислений содержит число 45 и не содержит 58?