ФИПИ тапсырмаларының шешімдері ЕГЭ по информатикаға: «Графы и пути» — жауаптарымен

Подсчёт путей через город Ж

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассматриваем только ориентированные дороги и исключаем из схемы город К вместе с дорогами, которые через него проходят.
2. 2
   Для каждой вершины определяем число путей из города А: значение в вершине равно сумме значений во всех вершинах, из которых в неё ведут стрелки.$$N(v)=\sum_{u\to v}N(u)$$

Ещё 2 қадам — толық шешімде

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схема дорог задаёт ориентированный граф. Длину максимального пути до каждого города вычисляем по направлению стрелок, начиная с города А.$$d(А)=0$$
2. 2
   При переходе по каждой дороге увеличиваем длину пути на единицу. Если в город ведут несколько дорог, сохраняем наибольшее из полученных значений.$$d(Y)=\max_{X\to Y}(d(X)+1)$$

Ещё 1 қадам — толық шешімде

Пути через заданный город

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассмотрим только пути, проходящие через город В. Каждый такой путь однозначно состоит из пути из А в В и пути из В в М.$$N = N_{A\to В}\cdot N_{В\to M}$$
2. 2
   Для подсчёта количества путей используем динамический подсчёт: число путей в вершину равно сумме чисел путей в вершины, из которых в неё ведут стрелки.

Ещё 1 қадам — толық шешімде

Пути через город Г

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Г, однозначно представляется как путь из А в Г и путь из Г в М.
2. 2
   Для подсчёта количества путей в каждой вершине используем динамическое правило: число путей в вершину равно сумме чисел путей во все непосредственно предшествующие вершины.

Ещё 1 қадам — толық шешімде

Пути через город Г

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Г, однозначно состоит из пути из А в Г и пути из Г в М.$$N = N_{АГ} \cdot N_{ГМ}$$
2. 2
   Подсчётом по схеме получаем 4 пути из А в Г и 7 путей из Г в М.$$N = 4 \cdot 7 = 28$$

Пути через город Г

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Г, однозначно раскладывается на путь из А в Г и путь из Г в М.
2. 2
   Для подсчёта числа путей в ориентированной схеме последовательно складываем количества путей, приходящих в каждую вершину, начиная с города А.

Ещё 1 қадам — толық шешімде

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схему дорог рассматриваем как ориентированный граф: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Для каждой вершины вычисляем длину самого длинного пути из города А. При переходе по одной дороге длина увеличивается на 1.

Ещё 1 қадам — толық шешімде

Пути через город Л

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассматриваем только пути, проходящие через город Л. Каждый такой путь однозначно разбивается на путь из А в Л и путь из Л в М.$$N_{А\to М\ через\ Л}=N_{А\to Л}\cdot N_{Л\to М}$$
2. 2
   Для ориентированной схемы дорог последовательно подсчитываем число путей до вершин, складывая количества путей до всех их непосредственных предшественников. По рисунку произведение числа путей из А в Л и из Л в М равно 20.$$N_{А\to Л}\cdot N_{Л\to М}=20$$

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схема дорог задаёт ориентированный граф: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Для каждого города подсчитываем максимальную длину пути из города А, переходя по рёбрам только в направлении стрелок.

Ещё 1 қадам — толық шешімде

Оптимальный маршрут робота

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…

1. 1
   Робот движется только вправо и вниз, поэтому в каждую клетку он может попасть только сверху или слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
2. 2
   Для минимальной суммы используется аналогичная рекуррентная формула с минимумом.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

Ещё 1 қадам — толық шешімде

Максимальная цепочка пар

Текстовый файл состоит из символов A, B и C. Определите максимальное количество идущих подряд пар символов AC или BC в прилагаемом файле. Искомая подпоследовательность должна состоять только из пар…

1. 1
   Разобьём проверяемую последовательность на идущие подряд непересекающиеся пары символов.
2. 2
   Пара является подходящей, если имеет вид AC или BC, то есть её второй символ равен C, а первый символ — A или B.$$pair = (s[i] = A \lor s[i] = B) \land (s[i+1] = C)$$

Ещё 1 қадам — толық шешімде

Кластеризация звёздных точек

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество…

1. 1
   Считать координаты точек из файлов А и Б. Для файла Б временно рассматривать все точки, включая три аномалии.
2. 2
   Разбить точки на кластеры. Две точки относятся к одному кластеру, если их можно включить в общий прямоугольник со сторонами $H$ и $W$; итоговые прямоугольники кластеров не пересекаются.

Ещё 5 қадам — толық шешімде

Кластеризация звёздных точек

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо выполнить кластеризацию точек-звёзд на непересекающиеся кластеры, помещаемые в прямоугольники со…

1. 1
   Считать координаты и характеристики звёзд из файлов А и Б.
2. 2
   Разбить точки каждого файла на единственные кластеры, удовлетворяющие условию размещения в непересекающихся прямоугольниках.

Ещё 4 қадам — толық шешімде

Кластеризация звёздных точек

Задание выполняется с использованием прилагаемых файлов. В файлах A и Б записаны координаты точек на плоскости. В файле A находятся точки двух кластеров, каждый из которых помещается в прямоугольник…

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

Ещё 3 қадам — толық шешімде