Между городами А, Б, В, Г, Д, Е, Ж, З, И, К, Л заданы… — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: высокая

Между городами А, Б, В, Г, Д, Е, Ж, З, И, К, Л заданы дороги с односторонним движением. Ниже перечислены все дороги. Число в скобках — стоимость… Ответ и подробный разбор. ЕГЭ по информатике, тема «Пути в графе».

Условие

Между городами А, Б, В, Г, Д, Е, Ж, З, И, К, Л заданы дороги с односторонним движением.
Ниже перечислены все дороги. Число в скобках — стоимость проезда по дороге в условных единицах.

Из А — в Б (3), Г (4).
Из Б — в В (1), Г (4).
Из В — в Г (4), Д (1), Ж (3).
Из Г — в Д (1), Е (2), И (3).
Из Д — в Е (2), И (3).
Из Е — в Ж (4), З (1).
Из Ж — в З (1), И (2).
Из З — в И (1), К (4).
Из И — в К (2), Л (4).
Из К — в Л (1).

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

Сколько существует путей из А в Л, которые проходят через Е и имеют стоимость ровно 16?

Ответ и разбор

Ответ: 12

Разобьём путь в обязательном городе Е. В ациклическом графе он встречается не более одного раза: любой подходящий путь однозначно состоит из участка А → Е и участка Е → Л.

Одних общих чисел путей на участках недостаточно: их стоимости должны в сумме дать ровно 16. Сохраняем отдельный счётчик для каждой стоимости.

F(v, s) — число путей из А в v со стоимостью ровно s. База F(А, 0) = 1: это единственный пустой путь в начальный город, без дорог и затрат. Остальные начальные состояния равны 0.

Считаем вершины в приведённом порядке. Для каждой входящей дороги u → v стоимости c прибавляем F(u, s − c) к F(v, s). Каждое продолжение имеет единственную последнюю дорогу, поэтому такой подсчёт не теряет и не дублирует пути; при отрицательной стоимости значение равно 0.

В списках запись «стоимость → количество» означает число путей именно этой стоимости. Показаны все ненулевые состояния, без отсечения по бюджету; не перечисленные стоимости имеют количество 0.

Первый участок: А → Е, распределения F:

  • Город А: 0 → 1.
  • Город Б: 3 → 1.
  • Город В: 4 → 1.
  • Город Г: 4 → 1; 7 → 1; 8 → 1.
  • Город Д: 5 → 2; 8 → 1; 9 → 1.
  • Город Е: 6 → 1; 7 → 2; 9 → 1; 10 → 2; 11 → 1.

Проверка: F(Д, 5) = F(В, 4) + F(Г, 4) = 1 + 1 = 2 — клетка сходится.

Второй участок: Е → Л, распределения G. Начинаем заново с G(Е, 0) = 1 (пустой путь); переход тот же.

  • Город Е: 0 → 1.
  • Город Ж: 4 → 1.
  • Город З: 1 → 1; 5 → 1.
  • Город И: 2 → 1; 6 → 2.
  • Город К: 4 → 1; 5 → 1; 8 → 2; 9 → 1.
  • Город Л: 5 → 1; 6 → 2; 9 → 2; 10 → 3.

Проверка: G(И, 6) = G(Ж, 4) + G(З, 5) = 1 + 1 = 2 — клетка сходится.

Сочетаем только дополняющие стоимости: если первый участок стоит s, второй должен стоить 16 − s. Для фиксированной пары любой первый путь можно соединить с любым вторым: ранние и поздние вершины не пересекаются, кроме Е. Разные пары стоимостей не смешиваются.

  • 6 + 10 = 16: 1 · 3 = 3.
  • 7 + 9 = 16: 2 · 2 = 4.
  • 10 + 6 = 16: 2 · 2 = 4.
  • 11 + 5 = 16: 1 · 1 = 1.

Другие пары не дают нужной суммы или имеют нулевое количество путей. Всего: 3 + 4 + 4 + 1 = 12.

Частая ошибка

Ловушка: произведение общих чисел путей учитывает и другие стоимости; подсчёт всех путей нужной стоимости дополнительно захватил бы пути в обход Е.

Ответ: 12.

Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-paths-high-11

Открыть тренажёр

В UTF-8 латинская A занимает один байт, а русская Я — два. В этой кодировке одна кодовая позиция Unicode занимает от одного до четырёх байтов, поэтому длина текста в байтах не обязана совпадать с числом букв.

Формулы и приём

Подсчёт путей в графе

Как быстро посчитать все пути из А в К по стрелкам?

путей в вершину = сумма путей во все вершины, откуда ведёт стрелка · путей в старт = 1

Подписывай у каждой вершины число путей до неё: у старта единица, у любой другой — сумма чисел всех вершин, из которых в неё идёт стрелка. Если в Г ведут стрелки из Б (3 пути) и В (2 пути), то до Г ровно 3 + 2 = 5 путей. Обходи вершины по направлению стрелок, пока не дойдёшь до конечной.

Пути «через вершину Д» — перемножь число путей от старта до Д и от Д до финиша. Пути «не через Д» — из общего числа путей вычти проходящие через Д.

Рядом

Продолжить тренировку

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

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.