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

1. 1. Ставим в стартовую вершину единицу: А = 1. Дальше идём так, чтобы к моменту подсчёта вершины все её предшественники уже были посчитаны.
2. 2. В Б ведёт только ребро из А, значит Б = 1. В В тоже только из А, значит В = 1.
3. 3. В Г ведут два ребра — из Б и из В: Г = Б + В = 1 + 1 = 2.
4. 4. В Д ведёт одно ребро из В: Д = 1.
5. 5. В Е ведут рёбра из Г и Д: Е = Г + Д = 2 + 1 = 3. В Ж ведёт ребро из Д: Ж = 1.
6. 6. В К ведут рёбра из Е и Ж: К = Е + Ж = 3 + 1 = 4. Ответ — 4 пути. Заметь: сами пути мы не выписывали ни разу, и именно поэтому приём работает на графе из двухсот рёбер.

Ответ: 4

1. 1.

   from functools import lru_cache
   import sys
   sys.setrecursionlimit(100000)

   otkuda = {}                       # вершина -> список тех, из кого в неё ведёт ребро
   for line in open('23.txt'):

   L, M = map(int, line.split()) otkuda.setdefault(M, []).append(L)

   @lru_cache(None)
   def putey(v):
       if v == 1:
           return 1                  # в стартовую вершину ведёт один путь — пустой
       return sum(putey(u) for u in otkuda.get(v, []))

   print(putey(150))

2. 2. Шаг 1. Направление словаря. Храним для каждой вершины список тех, из кого в неё ведут рёбра, а не наоборот. Так рекурсия идёт от цели назад к старту и на каждом шаге просто складывает уже посчитанные значения.
3. 3. Шаг 2. База рекурсии — стартовая вершина, а не отсутствие рёбер. В вершину 1 ведёт ровно один путь: пустой, из неё самой. Если бы базой было «нет входящих рёбер, значит ноль», ответ получился бы нулевым всегда.
4. 4. Шаг 3. otkuda.get(v, []) вместо otkuda[v] — для вершин, в которые вообще ничего не ведёт. Такие в графе бывают, и обычное обращение по ключу упало бы с ошибкой.
5. 5. Шаг 4. Трассировка на нашем маленьком графе. В вершину 1 ведёт 1 путь. В вершину 2 ведёт ребро только из 1, значит путей 1. В вершину 3 тоже 1.
6. 6. Шаг 5. В вершину 4 ведут рёбра из 2 и 3: путей 1 + 1 = 2. Это пути 1→2→4 и 1→3→4.
7. 7. Шаг 6. В вершину 5 ведёт ребро только из 3: путей 1.
8. 8. Шаг 7. В вершину 6 ведут рёбра из 4 и 5: путей 2 + 1 = 3.
9. 9. Шаг 8. В вершину 7 ведут рёбра из 5 и 6: путей 1 + 3 = 4. Ответ: 4. Выпишем их для проверки: 1→3→5→7, 1→2→4→6→7, 1→3→4→6→7, 1→3→5→6→7. Действительно четыре.
10. 10. Шаг 9. Зачем lru_cache. Без него значение вершины 3 пересчитается для каждого пути, ведущего через неё, и общее число вызовов станет равным числу путей — а их в боевом файле бывают миллиарды. С кэшем каждая вершина считается ровно один раз, и работа пропорциональна числу рёбер.
11. 11. Шаг 10. sys.setrecursionlimit нужен потому, что глубина рекурсии равна длине самого длинного пути, а в графе на 300 вершин она может дойти до трёхсот. Стандартный предел в тысячу обычно хватает, но лишняя строка страховки не помешает.

Ответ: 4 для примера; на боевом файле программа печатает ответ

1. 1.

   from functools import lru_cache

   otkuda = {}
   for line in open('23.txt'):
       chasti = line.split()

   L, M = int(chasti[0]), int(chasti[1])

       ves = round(float(chasti[2]) * 10)      # переводим в целые десятые
       otkuda.setdefault(M, []).append((L, ves))

   BESKONECHNOST = float('inf')

   @lru_cache(None)
   def put(v):
       if v == 1:
           return 0
       return min((put(u) + w for u, w in otkuda.get(v, [])), default=BESKONECHNOST)

   print(put(300) // 10) # целая часть длины

2. 2. Шаг 1. Отличий от предыдущей программы ровно три: сумма заменена на минимум, база даёт 0 вместо 1, и веса переводятся в целые. Всё остальное — тот же обход по входящим рёбрам с тем же кэшем.
3. 3. Шаг 2. Почему целые десятые. Веса в условии — вещественные числа вида 4.2, и складывать их напрямую опасно. Пример: веса 3.8, 7.1, 3.3, 9.2, 6.2, 4.1 и 1.3 в сумме дают ровно 35,0, но при сложении во float получается 34.99999999999999, и int от этого числа равен 34. Ответ уезжает на единицу, а заметить это невозможно.
4. 4. Шаг 3. round(float(x) * 10) вместо int(float(x) * 10). Причина та же: 4.2 * 10 во float даёт 41.99999999999999, и int отрезал бы до 41. round берёт ближайшее целое и даёт 42.
5. 5. Шаг 4. Трассировка. Переводим веса в десятые: 42, 15, 23, 61, 22, 11, 33, 99, 4. Расстояние до вершины 1 равно 0.
6. 6. Шаг 5. Вершина 2: единственное входящее ребро из 1 весом 42 → 42. Вершина 3: ребро из 1 весом 15 → 15.
7. 7. Шаг 6. Вершина 4: два входящих ребра — из 2 (42 + 23 = 65) и из 3 (15 + 61 = 76). Берём минимум: 65.
8. 8. Шаг 7. Вершина 5: ребро из 3 весом 22 → 15 + 22 = 37.
9. 9. Шаг 8. Вершина 6: из 4 даёт 65 + 11 = 76, из 5 даёт 37 + 33 = 70. Минимум 70.
10. 10. Шаг 9. Вершина 7: из 5 даёт 37 + 99 = 136, из 6 даёт 70 + 4 = 74. Минимум 74 десятых, то есть длина пути 7,4, а целая часть 7.
11. 11. Шаг 10. Проверка выписыванием: кратчайший путь 1→3→5→6→7 длиной 1,5 + 2,2 + 3,3 + 0,4 = 7,4 ✔ Соседний путь 1→2→4→6→7 даёт 4,2 + 2,3 + 1,1 + 0,4 = 8,0 — длиннее.
12. 12. Шаг 11. Деление // 10 в последней строке — это и есть «целая часть длины»: 74 десятых дают 7. Обычное деление вернуло бы 7.4, и целую часть пришлось бы отрезать ещё раз.

Ответ: 7

1. 1. Шаг 1. Сначала повторим базовый расчёт: путей из 1 в 7 всего 4, а по вершинам значения такие — в 1 один путь, во 2 один, в 3 один, в 4 два, в 5 один, в 6 три, в 7 четыре.
2. 2. Шаг 2. Пути через вершину 4. Граф ориентированный и ациклический, значит вершина встречается в пути не более одного раза и разрезает его на два независимых куска: из 1 в 4 и из 4 в 7. Количества перемножаются.
3. 3. Шаг 3. Путей из 1 в 4 — два (это уже посчитано: 1→2→4 и 1→3→4). Путей из 4 в 7 считаем отдельно: из 4 ведёт единственное ребро в 6, а из 6 — единственное в 7, значит путь один.
4. 4. Шаг 4. Ответ на первый вопрос: 2 · 1 = 2 пути. Выпишем для проверки: 1→2→4→6→7 и 1→3→4→6→7 ✔
5. 5. Шаг 5. Пути в обход вершины 6. Запрет обрабатывается иначе, чем обязательная вершина: запрещённой вершине просто присваивается ноль путей, и она перестаёт что-либо передавать дальше.
6. 6. Шаг 6. Пересчитываем с нулём в шестёрке: в 1 один путь, во 2 один, в 3 один, в 4 два, в 5 один, в 6 ноль, в 7 — сумма по входящим рёбрам из 5 и 6, то есть 1 + 0 = 1.
7. 7. Шаг 7. Ответ на второй вопрос: один путь, и это 1→3→5→7 ✔ Остальные три пути из четырёх действительно проходят через шестёрку.
8. 8.

   Шаг 8. То же программой — меняются две строки:

   @lru_cache(None)
   def putey(v, zapret=6):
       if v == zapret:
           return 0
       if v == 1:
           return 1
       return sum(putey(u) for u in otkuda.get(v, []))

   print(putey(7))                       # в обход запрещённой
   print(putey_bez_zapreta(4) * putey_ot(4, 7))   # через обязательную

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

Ответ: 2 пути через вершину 4; 1 путь в обход вершины 6