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

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

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?

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

1. Прибавь 2

2. Прибавь сумму цифр

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

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

1. Прибавь 3

2. Умножь на 4

3. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. У исполнителя есть запас энергии, который в начальный момент равен 700. При выполнении каждой команды над текущим числом на экране исполнитель расходует энергию равную 10 единиц. Сколько существует различных программ, преобразующих число 1 в число 4400, после выполнения которых запас энергии точно равен 0?

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

1. Прибавь 3

2. Умножь на 4

3. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. У исполнителя есть запас энергии, который в начальный момент равен 1000. При выполнении каждой команды над текущим числом на экране исполнитель расходует энергию равную количеству цифр этого числа. Сколько существует различных программ, преобразующих число 1 в число 5500, после выполнения которых запас энергии точно равен 0?

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

1. Прибавь 3

2. Умножь на 4

3. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. У исполнителя есть запас энергии, который в начальный момент равен 1000. При выполнении каждой команды над текущим числом на экране исполнитель расходует энергию равную количеству цифр этого числа. Сколько существует различных программ, преобразующих число 1 в число 5500, для выполнения которых хватит запаса энергии?

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

1. Прибавь 3

2. Умножь на 4

3. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. У исполнителя есть запас энергии, который в начальный момент равен 500. При выполнении каждой команды над текущим числом на экране исполнитель расходует энергию равную сумме цифр этого числа. Сколько существует различных программ, преобразующих число 1 в число 2000, для выполнения которых хватит запаса энергии?

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

1. прибавь 1

2. прибавь 3

3. вычти 1

4. вычти 3

Сколько существует программ, для которых при исходном числе 42 результатом будет являться число 42, при этом траектория вычисления может содержать только числа от 40 до 49, притом каждое число не более одного раза.

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

1. прибавь 1

2. умножь на 2

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

Какое количество команд «прибавь 1» выполнит исполнитель, преобразуя число 1 в число 16, при условии, что он потратил минимально возможное количество энергии?