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

(А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 1

2. Вычесть 2

3. Извлечь корень

Первые две команды уменьшают число на доске на 1 и 2 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько различных результатов можно получить из исходного числа 113 в ходе исполнения программы, содержащей ровно 17 команд?

(А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 1

2. Вычесть 2

3. Извлечь корень

Первые две команды уменьшают число на доске на 1 и 2 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 27 в число 6, содержат в траектории число 18, но не содержит число 20?

(А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 2

2. Вычесть 4

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 4 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 46 в число 2 и содержат в траектории числа 32 и 12?

(А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 3

2. Вычесть 4

3. Извлечь корень

Первые две команды уменьшают число на доске на 3 и 4 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 36 в число 3 и содержат в траектории число 21?

(А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

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

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 38, и при этом траектория вычислений содержит числа 15 и 30, а также не содержит чисел 12 и 20. Также программа не должна содержать двух команд «Умножь на 3» подряд.

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 43, и при этом траектория вычислений содержит число 15 и не содержит чисел 25 и 30. Также программа не должна содержать двух команд «Умножь на 3» подряд.

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 60, и при этом траектория вычислений содержит число 20 и не содержит чисел 30 и 40. Также программа не должна содержать двух команд «Умножь на 2» подряд.

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 51, и при этом траектория вычислений содержит число 18 и не содержит число 33. Также программа не должна содержать двух команд «Умножь на 2» подряд.

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 93, и при этом траектория вычислений содержит число 10 и не содержит число 28. Также программа не должна содержать двух команд «Прибавь 1» подряд.

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 79, и при этом траектория вычислений содержит число 11 и не содержит число 23. Также программа не должна содержать двух команд «Прибавь 1» подряд.

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

1. Прибавь к первому числу 3

2. Умножь первое число на 4

3. Прибавь ко второму числу 5

4. Умножь второе число на 2

Первая из них увеличивает первое число из пары на 2, вторая – умножает его на 4. Третья команда увеличивает второе число из пары на 5, четвертая – умножает его на 2. Сколько различных пар взаимно простых чисел можно получить из пары чисел (2, 3) с помощью программы, которая состоит ровно из 5 команд? Пары, отличающиеся только перестановкой чисел, считать одинаковыми.

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

1. Прибавь 3

2. Вычти 1

Первая команда увеличивает число на экране на 3, вторая уменьшает его на 1. Программа для исполнителя – это последовательность команд. Будем называть циклической программу, при выполнении которой исполнитель на каком-то этапе вновь получает начальное число и далее поcледовательность команд повторяется. Например, циклической является программа следующих преобразований: 1 4 3 2 1 4. Сколько существует циклических программ, состоящих из 9 команд?

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

1. Прибавь 4

2. Прибавь 7

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

Первая команда увеличивает число на экране на 4, вторая увеличивает его на 7, третья делит на 2 нацело (остаток отбрасывается). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые состоят из 10 команд и при исходном числе 1 результатом является 1?

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

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

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

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

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

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

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

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

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

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

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

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