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

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

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?» (символ «?» означает ровно один произвольный символ; символ «*» означает любую последовательность символов произвольной длины; в том числе «*» может задавать и пустую последовательность) и не содержит двух идущих подряд одинаковых команд?

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

A. Вычти 2

B. Вычти 3

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

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

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

A. Прибавь 2

B. Умножь на 2

C. Умножь на 4

Первая команда увеличивает число на 2 раза, вторая – в 2 раза, третья – в 4 раза. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом будет являться число 24, при этом траектория вычисления не содержит подпоследовательность команд BACA. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы BCA при исходном числе 4 траектория будет состоять из чисел 8, 32, 34.

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

A. Умножь на 2

B. Прибавь 2

Первая команда увеличивает число в 2 раза, вторая – на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом будет являться число 42, при этом траектория вычисления не содержит подпоследовательность команд BBA. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы ABA при исходном числе 4 траектория будет состоять из чисел 8, 10, 20.

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

1. Прибавь 1

2. Умножь на 2

Первая команда увеличивает число на 1, вторая – вдвое. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 или 7 результатом является число 43 или 47, при этом траектория вычислений содержит число 20? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

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

A. Прибавь 2

B. Прибавь 3

Первая команда увеличивает число на 2, вторая – на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 15 результатом будет являться число 34, при этом траектория вычисления содержит ровно 3 простых числа. Траектория вычисления программы – это последовательности результатов выполнения всех команд. Например, для программы ABA при исходном числе 4 траектория будет состоять из чисел 6, 9, 11 и содержать одно простое число 11.

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

A. Прибавь 1

B. Умножь на 2

С. Умножь на 3

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

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

A. Умножь на 2

B. Прибавь 3

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