Разбор 23 задания ЕГЭ по информатике

Результат: 28

• Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:



1. 5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
2. 35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
3. 35 -> 105 — «ненужная» часть траектории;
4. 105 -> 250 — тоже «ненужная» часть.
• Чтобы вычислить результат, т.е. количество программ, необходимо:

траектория 1 * (траектория 2 - (траектория 3 * траектория 4))

полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий

• Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
• Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
• Расчет отрезка 1: 5 -> 35
• Возьмем такое наименьшее число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:

5 не подходит: применимы две команды в интервале до 35: 
5 + 5 = 10 и 5 * 5 = 25
10 подходит: применима только одна команда:
10 + 5 = 15, а 10 * 5 = 50 - больше 35

• Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):



• Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):



• Итого получили две программы.

Результат: 2

• Расчет отрезка 2: 35 -> 250
• Возьмем такое наименьшее число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:

55 
т.к. 55 * 5 = 275 - это больше числа 250

• Затем будем последовательно брать подходящие меньшие числа



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

• для числа 45 мы взяли результат, полученный для числа 50 (2);
• для числа 40 мы взяли результат, полученный для числа 45 (3);
• для числа 35 мы взяли результат, полученный для числа 40 (4);

Результат: 5

• Расчет отрезка 3: 35 -> 105
• Возьмем такое наименьшее число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:

35 
т.к. 35 * 5 = 175 - больше числа 105



Результат: 1

• Расчет траектории 4: 105 -> 250


Результат: 1

• Посчитаем результат, согласно полученной формуле:

траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
2 * (5 - 1 * 1) = 8

Результат: 8

• Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:

12 
к нему применима только команда - прибавь 1 
12 * 4 = 48 - это больше, чем 44 

• Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):


Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

• Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.


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

• для 11 взят результат, полученный для 12 (1);
• для 10 взят результат, полученный для числа 11 (2);
• для 9 взят результат, полученный для 10 (3);
• и т.д.
• Для последнего числа 3 получено 10 команд.

Результат: 10

• Изобразим траекторию в виде луча, на котором отложим отрезки:



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

1 * 2 * 3
или
(2 -> 8) * (8 -> 10) * (10 -> 12)

• Найдем отдельно количество программ каждого из отрезков:
• 2 -> 8 = 15
• На интервале от 2 до 8 возьмем число, для которого исполнима только одна из команд:

7
7 + 1 = 8
7 + 2 = 9 - нельзя, вне интервала

• Рассмотрим все числа интервала, двигаясь от большего к меньшему:



• 8 -> 10 = 2
• очевидно, что это две программы:



• 10 -> 12 = 2



• Выполним произведение полученных результатов:

15 * 2 * 2 = 60

Результат: 60