Задание 13 ЕГЭ по информатике

1. 1.

   from functools import lru_cache
   @lru_cache(None)
   def f(a):
       if a == 10: return 1
       if a > 10: return 0
       return f(a+1) + f(a*2)   # две команды: +1 и *2
   print(f(3))
   # для 'траектория содержит X' считаем f(start->X) * f(X->end)
   # для 'не содержит Y' возвращаем 0 при a == Y

Ответ: Рекурсия с кэшем считает число программ

1. 1. Обозначаем N(x) — число программ, переводящих 2 в x. База: N(2) = 1.
2. 2. Правило: N(x) = N(x − 1) + N(x / 2), причём второе слагаемое учитывается только если x чётное и x / 2 не меньше стартового числа 2 (иначе такая вершина недостижима и в подсчёте не участвует).
3. 3.

   Считаем по возрастанию. N(3) = N(2) = 1 (умножение не даёт 3, число нечётное). N(4) = N(3) + N(2) = 1 + 1 = 2. N(5) = N(4) = 2. N(6) = N(5) + N(3) = 2 + 1 = 3. N(7) = N(6) = 3.

4. 4.

   Продолжаем. N(8) = N(7) + N(4) = 3 + 2 = 5. N(9) = N(8) = 5. N(10) = N(9) + N(5) = 5 + 2 = 7. N(11) = N(10) = 7. N(12) = N(11) + N(6) = 7 + 3 = 10.

5. 5. Проверка здравым смыслом: числа в таблице растут монотонно, каждое следующее не меньше предыдущего — так и должно быть, потому что любую программу до x − 1 можно продолжить командой «прибавь 1».
6. 6. Если бы условие требовало «не проходить через 7», мы поставили бы N(7) = 0 и пересчитали: N(8) = 0 + 2 = 2, N(9) = 2, N(10) = 2 + 2 = 4, N(11) = 4, N(12) = 4 + 3 = 7.

Ответ: 10

1. 1. Шаг 1. Разрезаем по обязательному числу: ответ = (число программ 16 → 7) · (число программ 7 → 3). Считаем участки по отдельности.
2. 2. Шаг 2. Первый участок, цель 7. Заполняем таблицу снизу вверх, начиная с цели. f(7) = 1 (пустая программа).
3. 3. f(8): команда A даёт 8 // 2 = 4, это меньше цели 7 — тупик. Команда B даёт 7 — это цель, f(7) = 1. Итого f(8) = 1.
4. 4. f(9): A даёт 4 (мимо), B даёт 8. f(9) = f(8) = 1. Так же f(10) = 1, f(11) = 1, f(12) = 1 — у всех единственный путь вниз по единичкам, потому что деление пополам уводит ниже семёрки.
5. 5. f(13): число запрещено условием, значит f(13) = 0. Ни одна траектория не имеет права через него проходить.
6. 6. f(14): A даёт 14 // 2 = 7 — это цель, вклад 1. B даёт 13, а f(13) = 0 — вклад ноль. Итого f(14) = 1.
7. 7. f(15): A даёт 7 — вклад f(7) = 1. B даёт 14 — вклад f(14) = 1. Итого f(15) = 2.
8. 8. f(16): A даёт 8 — вклад f(8) = 1. B даёт 15 — вклад f(15) = 2. Итого f(16) = 3.
9. 9. Шаг 3. Второй участок, цель 3. f(3) = 1. f(4): A даёт 2 (меньше цели, мимо), B даёт 3 — вклад 1, значит f(4) = 1. f(5): A даёт 2 (мимо), B даёт 4 — f(5) = 1. f(6): A даёт 3 — вклад 1, B даёт 5 — вклад 1, значит f(6) = 2. f(7): A даёт 3 — вклад 1, B даёт 6 — вклад 2, значит f(7) = 3.
10. 10. Шаг 4. Перемножаем участки: 3 · 3 = 9.
11. 11. Шаг 5. Проверка здравым смыслом. Три пути из 16 в 7 — это 16→8→7, 16→15→7 и 16→15→14→7. Действительно три, и ни один не задевает тринадцать. Три пути из 7 в 3 — это 7→3, 7→6→3 и 7→6→5→4→3. Каждый первый сочетается с каждым вторым: 3 · 3 = 9 программ ✔

Ответ: 9

1. 1.

   from functools import lru_cache

   START, GOAL = 16, 3

   MUST = 7                 # обязательное число; None, если его нет
   BAD = {13}               # запрещённые числа; пустое множество, если их нет
   KOMANDY = [lambda x: x // 2, lambda x: x - 1]

   @lru_cache(None)
   def f(x, cel):
       if x == cel:
           return 1             # база: пустая программа
       if x < cel:
           return 0             # команды только уменьшают — цель уже позади
       s = 0
       for k in KOMANDY:
           y = k(x)
           if y < cel or y in BAD or y == x:
               continue
           s += f(y, cel)
       return s

   if MUST is None:
       print(f(START, GOAL))
   else:
       print(f(START, MUST) * f(MUST, GOAL))

2. 2. Шаг 1. Все особенности задания вынесены в четыре строки наверху: старт и цель, обязательное число, запрещённые числа, список команд. Под новое задание меняются только они, а тело функции остаётся прежним — это и делает программу универсальной.
3. 3. Шаг 2. Команды заданы списком функций. lambda x: x // 2 — это «найди целую часть от деления на 2», lambda x: x - 3 — «вычесть 3». Добавить третью команду значит дописать ещё одну лямбду в список.
4. 4. Шаг 3. Проверка y == x нужна для команд, которые на некоторых числах ничего не меняют: 1 // 2 даёт 0, а вот при делении единицы на единицу или при вычитании нуля программа зациклилась бы. Это дешёвая страховка.
5. 5. Шаг 4. Проверка на трёх реальных заданиях банка. Команды //2 и −1, из 16 в 3, без 13, через 7 — программа печатает 9. Команды //2, −3 и −2, из 28 в 4, без 13, через 10 — печатает 141. Команды −1, //3 и −3, из 23 в 2, без 18, через 4 — печатает 415. Все три совпали с эталонными ответами банка.
6. 6. Шаг 5. Если команды увеличивают число (например, «прибавить 2» и «прибавить 10»), меняются два отсечения: вместо x < cel пишем x > cel, и вместо y < cel — y > cel. Логика остаётся той же. Так решается задание «сколько программ переводят 5 в 71» — ответ 5411, и руками такую таблицу заполнять долго.
7. 7. Шаг 6. Сколько это стоит по времени. Различных значений x не больше, чем расстояние от старта до цели, то есть несколько десятков. С кэшем каждое считается один раз — работа мгновенная. Без кэша та же задача про 5 → 71 потребовала бы миллиарды вызовов.

Ответ: 9, 141 и 415 — совпадают с ответами банка

1. 1. Шаг 1. Здесь обе команды увеличивают число, поэтому таблицу удобнее заполнять от цели вниз: f(71) = 1, а f(x) считается через f(x + 2) и f(x + 10). Отсечение тоже переворачивается: f(x) = 0 при x > 71, потому что перепрыгнув цель, вернуться к ней нечем.
2. 2. Шаг 2. Обе команды меняют чётность одинаково — прибавляют чётное число. Значит, из нечётной пятёрки достижимы только нечётные числа, и 71 среди них. Все чётные значения можно в таблицу не вписывать вовсе: это вдвое сокращает работу.
3. 3. Шаг 3. Заполняем сверху вниз. f(71) = 1. f(69): +2 даёт 71 (вклад 1), +10 даёт 79 — больше цели, ноль. Итого f(69) = 1. Так же f(67) = f(65) = f(63) = 1: до 61 прыжок на десять всегда перелетает цель.
4. 4. Шаг 4. f(61): +2 даёт 63 (вклад 1), +10 даёт 71 — это цель, вклад 1. Итого f(61) = 2. Здесь длинная команда впервые попадает в цель, и значения начинают расти.
5. 5. Шаг 5. f(59): +2 даёт 61 (вклад 2), +10 даёт 69 (вклад 1). Итого f(59) = 3. f(57): +2 даёт 59 (3), +10 даёт 67 (1) — 4. f(55): +2 даёт 57 (4), +10 даёт 65 (1) — 5.
6. 6.

   Шаг 6. Дальше числа растут быстро, и вручную заполнять таблицу до пятёрки — это двадцать три строки. Проще поменять в универсальной программе четыре строки настроек:

   START, GOAL = 5, 71

   MUST = None
   BAD = set()
   KOMANDY = [lambda x: x + 2, lambda x: x + 10]

   и перевернуть два отсечения: в первой проверке пишем if x > cel: return 0, а внутри цикла — if y > cel: continue.

7. 7. Шаг 7. Программа печатает 5411. Столько программ переводят 5 в 71 — и это хорошая иллюстрация к тому, почему их считают, а не выписывают: пять тысяч последовательностей команд руками не переберёшь.
8. 8. Шаг 8. Заметьте, как быстро растут значения: 1, 1, 1, 1, 2, 3, 4, 5… и к пятёрке уже пять тысяч. Рост тут примерно как у чисел Фибоначчи — каждое значение складывается из двух предыдущих, — и именно поэтому полный перебор без запоминания невозможен, а таблица с запоминанием считается мгновенно.

Ответ: 5411