Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза. Сколько существует программ, которые число 3 преобразуют в число 20 и в которых предпоследняя команда 1?
Для начала создадим таблицу "решений", где в ячейке с координатами (i, j) будет храниться количество программ, которые число i преобразуют в число j и в которых предпоследняя команда является командой 1. Здесь i и j принадлежат диапазону от 3 до 20.
Сначала заполним первую строчку таблицы. У нас имеется только одно число - 3, поэтому в каждой ячейке (3, j) записываем 1, если j равно 3, иначе - 0.
Далее заполняем остальные ячейки таблицы. Для этого каждой ячейке (i, j) будет соответствовать сумма значений ячеек (i-1, j-1) и (i-1, j/2), если j делится на 2 без остатка. В противном случае, значение ячейки (i, j) будет равно значению ячейки (i-1, j-1).
Таким образом, заполняя таблицу построчно, мы постепенно находим количество программ, преобразующих число 3 в число 20 и в которых предпоследняя команда 1. Нужное нам значение будет находиться в ячейке (20, 3).
Построение таблицы может быть выполнено следующим образом:
1. Создаем двумерный массив размером (18, 20) и заполняем его нулями.
2. Заполняем первую строчку массива, учитывая, что исходное число равно 3:
- Если j равно 3, то присваиваем ячейке (0, j) значение 1, иначе - 0.
3. В цикле с индексом i от 1 до 17 (включительно) и с индексом j от 3 до 20 (включительно) заполняем таблицу:
- Если j делится на 2 без остатка, то присваиваем ячейке (i, j) значение суммы ячеек (i-1, j-1) и (i-1, j/2).
- В противном случае, присваиваем ячейке (i, j) значение ячейки (i-1, j-1).
4. Выводим значение ячейки (17, 3), которая и будет являться ответом на задачу.
Таким образом, количество программ, которые число 3 преобразуют в число 20 и в которых предпоследняя команда 1, равно числу, хранящемуся в ячейке (17, 3).