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

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

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, при условии, что он потратил минимально возможное количество энергии?

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

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

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

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

1. прибавь 1

2. умножь на 2

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

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

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

1. прибавь 1

2. умножь на 2

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

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

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 3

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

Сколько существует программ, которые преобразуют исходное число 1 в число 49 так, что траектория вычисления не содержит чисел, в которых есть цифра 5?

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

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

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

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

1. Прибавь 1

2. Прибавь 7

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 7. Программой для исполнителя называется последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 61 так, что траектория вычисления не содержит чисел, в которых есть цифра 7?

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

1. Прибавь 1

2. Прибавь 3

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

Сколько существует программ, которые преобразуют исходное число 1 в число 45 так, что траектория вычисления не содержит чисел, в которых есть цифра 6?

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

1. Прибавь 1

2. Прибавь 5

Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – увеличивает на 5. Программой для исполнителя называется последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 30 так, что траектория вычисления не содержит чисел, в которых есть цифра 5?

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

A. Прибавь 3

B. Умножь на 4

C. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. Программой для исполнителя называется последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом будет являться число 725, при этом траектория вычисления содержит числа 16 и 152, и на промежутке траектории между этими числами последовательность команд является палиндромом. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы CAB при исходном числе 4 траектория будет состоять из чисел 20, 23, 92.

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

A. Прибавь 3

B. Умножь на 4

C. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. Программой для исполнителя называется последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом будет являться число 725, при этом траектория вычисления содержит числа 16 и 140, и содержит не более четырёх команд A на промежутке траектории между этими числами. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы CAB при исходном числе 4 траектория будет состоять из чисел 20, 23, 92.

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

A. Прибавь 3

B. Умножь на 4

C. Умножь на 5

Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – умножает на 4, выполняя третью – умножает на 5. Программой для исполнителя называется последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом будет являться число 725, при этом траектория вычисления содержит число 362, и не содержит команд B на промежутке траектории от начального до этого числа. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы CAB при исходном числе 4 траектория будет состоять из чисел 20, 23, 92.

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

1. Прибавь 1

2. Умножь на 2

3. Прибавь 3

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

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

A. Вычти 1

B. Вычти 2

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

Первая команда уменьшает число на экране на 1, вторая команда уменьшает число на экране на 2, третья команда заменяет число на экране на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 34 результатом будет являться число 2, при этом программа соответствует маске «?A*CB?» (символ «?» означает ровно один произвольный символ; символ «*» означает любую последовательность символов произвольной длины; в том числе «*» может задавать и пустую последовательность) и не содержит двух идущих подряд одинаковых команд?