Ах, задачки по информатике — это же как поход в зоопарк для программиста: вроде бы всё знакомо, но каждый раз можно встретить что-то неожиданное и забавное.
Вот недавно мы познакомились с типизацией задания ЕГЭ №23 и научились обходить запрещённые числа в вычислениях, словно хитрые туристы, которые знают, что нельзя трогать обезьяну, иначе она тебя покусает. Но теперь перед нами стоит обратная задача — сделать так, чтобы наш маршрут обязательно пролегал через некий «запретный плод», то есть число, которое должно обязательно появиться в траектории вычислений.
Представьте себе: вы едете из дома на дачу и знаете, что непременно должны зайти к бабушке за пирожками. Тут уже не получится объехать её стороной — пирожки зовут! Так и с числами: если условие говорит «обязательно через 4», значит путь должен пройти через 4.
Вспомним наш пример про превращение числа 1 в число 8 двумя командами: раньше мы учились обходить число 4 как неприветливого соседа, а теперь наоборот — ищем все дороги, ведущие именно через него.
Если взглянуть на все пути от 1 до 8 (а их у нас несколько), то оказывается, что только два из них проходят через заветную четвёрку. Это как если бы вы ехали из Москвы в Казань через Нижний Новгород: две дороги ведут до Нижнего и одна дорога — от Нижнего до Казани.
Сколько маршрутов? Правильно — два! Потому что каждая дорога до Нижнего может быть соединена с единственным путём дальше.
А теперь представим себе такую ситуацию: программист пишет код и вдруг осознаёт, что надо посчитать количество способов добраться от одного числа до другого с обязательной остановкой на промежуточном пункте.
Он сидит над этим весь вечер и думает: «Ну почему я не стал географом? Там хоть карты рисовать можно!» Но ведь комбинаторика — это весело! Если первый этап пути можно пройти m способами, а второй — n способами, то всего существует m × n способов пройти оба этапа подряд. Это как купить две футболки и три пары носков — сколько всего вариантов комплекта?
Правильно, шесть! Так и с путями.
В программировании эта идея реализуется просто: считаем количество способов добраться от стартового числа до обязательного промежуточного (f(1,4)), потом считаем способы добраться от этого промежуточного до конечного (f(4,8)) и перемножаем результаты. Получаем нужное количество маршрутов.
И вот тут начинается самое интересное — реальные задания!
Например, задание 2300 с исполнителем-командиром чисел. У него есть две команды: вычесть 2 или найти целую часть от деления на 2 (да-да, звучит страшно, но это просто целочисленное деление).
Задача звучит примерно так: сколько существует программ для преобразования числа 32 в число 1 так, чтобы обязательно встретилось число 14 по пути?
Звучит как шпионский квест: «Доберись из точки А в точку Б так быстро и незаметно… но обязательно загляни в точку Х». И вроде всё понятно — надо считать количество таких путей. В Python для этого используется оператор «//», который берёт целую часть от деления.
Кто-то говорит ему «целочисленное деление», кто-то просто «получить половинку без остатка». Главное — результат всегда будет целым числом!
Когда я впервые столкнулся с этой операцией на уроках информатики, меня спросили: «Что делает оператор //?» Я ответил серьёзно: «Он режет дроби пополам!» Учительница чуть не упала со стула от смеха. Но зато запомнил навсегда.