Алгоритм решения задания 13. Часть 2

Тип 2

В прошлой статье мы познакомились с типизацией 13 задания ЕГЭ по информатике и разобрали алгоритм решения первого типа.

Мы научились писать программу так, чтобы она «обходила» стороной запрещённые числа в траектории вычисления. Но теперь перед нами стоит обратная задача: траектория вычисления обязательно должна содержать какое-то число, заданное в условии.

Давайте рассмотрим, как это отразится на алгоритме решения.

Здесь легко запомнить готовую запись с произведением и так же легко забыть, откуда она взялась. Поэтому не будем начинать с кода. Сначала проживём задачу как настоящий маршрут с промежуточной остановкой.

Алгоритм решения

Снова вернёмся к нашему примеру с преобразованием числа 1 в число 8 двумя командами:

1. Прибавить 3
2. Умножить на 2

Ранее мы уже поняли, что для того, чтобы исключить число из траектории, нужно добавить его в базовый случай, при котором функция возвращает 0. Теперь рассмотрим обратную ситуацию: что, если траектория обязательно должна проходить через определённое число?

Допустим, мы хотим найти количество способов получить из 1 число 8 так, чтобы по пути обязательно встретилось число 4. Вспомним изображение всех возможных путей из 1 в 8 из самой первой статьи:

Действительно, четвёрка есть сразу в двух траекториях:

1. 1 → 2 → 4 → 8
2. 1→ 4 → 8

Давайте внимательно посмотрим на обе траектории и найдём нечто общее. Их можно разделить на две части:

1. Путь от 1 до 4 (1 → 2 → 4 и 1→ 4)
2. Путь от 4 до 8 (4 → 8 в обоих случаях)

То есть любая подходящая траектория выглядит так: сначала мы как-то добираемся от 1 до 4, а затем как-то добираемся от 4 до 8. Число 4 становится промежуточной точкой, через которую проходят все допустимые пути.

Вообразите турникет в коридоре: пройти из начала в конец можно разными дверями, но каждый допустимый маршрут обязан пересечь этот турникет. Всё, что было до него, и всё, что будет после, можно считать отдельно.

Это и есть главный поворот в задаче. Мы больше не пытаемся проверять обязательное число внутри каждой готовой траектории. Вместо этого заранее строим только такие маршруты, которые состоят из двух нужных участков.

Давайте разберём это на конкретном примере. Сначала найдём все способы добраться от 1 до 4. Их два:

• 1 → 2 → 4 (умножили на 2, потом ещё раз умножили на 2)
• 1 → 4 (прибавили 3)

Делаем вывод: обе команды могут привести из 1 к 4.

Теперь проверим два возможных первых шага из числа 4:

• 4 → 8 (умножили на 2)
• 4 → 7 → 8 (прибавили 3, потом… стоп, 7 нельзя превратить в 8 нашими командами)

Здесь же иная ситуация: из 4 в 8 может привести только одна команда (умножить на 2).

А теперь самое интересное. Каждый путь первого этапа можно «склеить» с каждым путём второго этапа.

Теперь перенесёмся с числовой прямой на дорогу. Представьте поездку из Москвы в Казань с обязательной остановкой в Нижнем Новгороде. Это условная схема, а не точная карта трасс: нам важен принцип выбора маршрута.

Ранним утром вы выезжаете из Москвы. До Нижнего Новгорода можно добраться двумя допустимыми дорогами: назовём их верхней и нижней. Какую бы вы ни выбрали, первая часть поездки закончится в одной точке — в Нижнем.

После остановки вы продолжаете путь в Казань. На нашей учебной схеме от Нижнего до Казани оставлена одна дорога. Значит, выбор на втором участке уже не зависит от того, как именно вы приехали в Нижний.

Берём первую дорогу до Нижнего, потом единственную дорогу до Казани — вот один маршрут.

Этому маршруту можно присвоить пару выборов: «первая дорога, единственное продолжение». Важно считать весь маршрут целиком, а не только первый участок.

Берём вторую дорогу до Нижнего, потом ту же дорогу до Казани — вот второй маршрут.

Вторая пара выглядит так: «вторая дорога, единственное продолжение». Других пар нет, поэтому получаем ровно два полных маршрута.

Если бы после Нижнего было три дороги, каждая из двух московских дорог могла бы продолжиться тремя способами. Получилось бы 2 × 3 = 6 сочетаний. Так произведение возникает не из программы, а из обычного перебора пар.

Итого: 2 × 1 = 2 маршрута.

В нашей задаче то же самое. Путь «1 → 2 → 4» можно продолжить путём «4 → 8», получим полный маршрут «1 → 2 → 4 → 8». Путь «1 → 4» тоже можно продолжить путём «4 → 8», получим «1 → 4 → 8». Два пути на первом этапе, один путь на втором — всего 2 × 1 = 2 полных маршрута через четвёрку.

На деле тут в силу вступает комбинаторика. Это классическое правило: если первое действие можно выполнить m способами, а второе — n способами, то общее количество способов выполнить оба действия последовательно равно m × n. В нашем случае «первое действие» — это путь от старта до обязательной точки, а «второе действие» — путь от обязательной точки до финиша.

Небольшой экскурс: от дорожных схем к графам

Задачи о маршрутах появились задолго до компьютеров. В XVIII веке Леонард Эйлер рассматривал прогулку по мостам Кёнигсберга и предложил отвлечься от длины дорог, оставив только точки и связи между ними.

Такой взгляд стал началом теории графов. В нашей задаче числа играют роль точек, команды — роль направленных дорог, а обязательное значение — роль города, через который маршрут должен пройти.

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

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

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

print(f(1, 8))

Теперь добавим обязательную точку нашего маршрута: число 4. То есть нужно найти количество способов получить из 1 число 8, при этом траектория вычислений должна содержать число 4. Для этого мы перемножим значения двух функций: f(1,4) и f(4,8):

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

print(f(1, 4) * f(4, 8))

В результате работы программы получаем ожидаемое число 2.

Функцию мы не меняли. Она по-прежнему умеет считать пути между любыми двумя границами. Изменился только вызов: вместо одного большого участка появились два маленьких, а их результаты были перемножены.

Это полезная привычка: сначала написать универсальный счётчик путей, а затем собрать ответ в print или отдельной переменной в точности по ограничениям из условия.

Пример 1

Теперь проверим этот подход на реальных заданиях. Начнём с такой формулировки:

№ 13000. Демоверсия 2021 Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1,…

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

1. Прибавить 1
2. Умножить на 2 

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя – это последовательность команд.

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Открыть задание

Сразу отметим новую для нас операцию: «Найти целую часть от деления на 2». Да, звучит запутанно, но на деле это не что иное, как целочисленное деление, которое выполняется в Python с помощью оператора «//».

Как уже говорилось ранее, первое условие в нашей функции никогда не меняется:

def f(x, y):
    if x == y:
        return 1

Мы ищем числа «вверх»: от 4 до 15. Следовательно, возвращать 0 будем если наше значение x превысит целевое значение (y).

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

Далее добавляется третье условие, в котором применяем указанные операции к аргументу x функции:

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 2, y) + f(x // 2, y)

И осталось лишь вывести на экран произведение двух функций — от 32 до 14 и от 14 до 1:

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 2, y) + f(x // 2, y)


print(f(32, 14) * f(14, 1))

В результате получаем число 54, которое и будет ответом на это задание.

Число 14 нельзя просто проверить условием внутри функции: такая проверка сказала бы лишь, попали мы в 14 сейчас или нет. Произведение гарантирует более сильное требование — каждый посчитанный полный маршрут действительно проходит через 14.

Пример 2

Рассмотрим похожее задание:

№ 13006. Основная волна 2022 Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает…

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

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

Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.

Открыть задание

Здесь даже половина операций идентична прошлому заданию! Переписываем предыдущий код и меняем 2 на 1 (в вычитании):

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 1, y) + f(x // 2, y)

И добавляем вывод на экран произведения двух функций:

def f(x, y):
    if x == y:
        return 1

    if x < y:
        return 0

    if x > y:
        return f(x - 1, y) + f(x // 2, y)


print(f(30, 12) * f(12, 1))

И получаем результат: число 376, которое и запишем в ответ.

Смысл ответа можно прочитать прямо по выражению: выбрать один путь из 30 в 12 и соединить его с одним путём из 12 в 1. Каждая уникальная пара даёт уникальную программу исполнителя.

Пример 3

Напоследок рассмотрим задание с такой формулировкой:

№ 13007. Основная волна 2022 Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Вычти 2 2. Найди целую часть от деления на 2 Первая из них уменьшает…

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

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

Первая из них уменьшает число на экране на 2, вторая заменяет число на экране на целую часть от деления числа на 2.

Программа для исполнителя – это последовательность команд.

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы 122 при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Открыть задание

Что же, теперь предстоит работать сразу с двумя числами в траектории. Но на деле это не добавит никаких сложностей, просто теперь будет произведение не двух, а трёх функций:

1. От 4 до 11 — f(4, 11)
2. От 11 до 13 — f(11, 13)
3. От 13 до 15 — f(13, 15)

А в коде это записывается так:

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)


print(f(4, 11) * f(11, 13)* f(13, 15))

Запускаем программу и получаем ответ — число 100.

Порядок обязательных точек тоже важен. Поскольку команды только увеличивают число, сначала можно пройти 11, а затем 13. Запись f(4, 13) * f(13, 11) здесь бессмысленна: вернуться с 13 к 11 такими командами нельзя.

Итоги

Во втором типе задания 13 траектория обязана пройти через заданное значение. Мы воспринимаем его как промежуточный пункт и делим весь путь на независимые участки.

Количество путей на участках перемножается, потому что каждый вариант первой части можно соединить с каждым вариантом второй. Для нескольких обязательных точек маршрут делится ещё сильнее — по одной части между каждой соседней парой точек.

Шаблон решения:

from functools import lru_cache

@lru_cache(None)
def f(x, target):
    if x == target:
        return 1
    if *1:
        return 0
    return f(*2, target) + f(*3, target)

answer = f(START, M) * f(M, FINISH)
print(answer)

Обозначения такие:

• *1 — проверка перескока цели;
• *2 и *3 — команды исполнителя;
• M — обязательная точка. Если обязательных точек две, добавьте третий множитель и расположите точки в достижимом порядке.

Да, в примерах к этой статье мы не использовали кеширования. Значения были не слишком большими, а программы работали достаточно быстро. Но если вы видите, что программа работает дольше обычного, то лучше пользуйтесь декоратором lru_cache.

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

В следующей статье объединим оба ограничения: траектория должна будет пройти через одно число и обойти другое.