Открытый вариант КИМ ЕГЭ по информатике 2024. Задание 27 решение

Условие задачи

Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна. Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.

6
8
20
5
13
7
19

Решение перебором

Сразу же напрашивается решение перебором, напишем его и подробно разберём.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

with open("A.txt", "r") as f:
    N = int(f.readline().strip())
    supplies = [int(f.readline().strip()) for line in range(N)]

min_cost = float('inf')
for mobile_point_idx in range(N):
    current_cost = 0
    for destination_idx in range(N):
        distance_if_straight = abs(mobile_point_idx - destination_idx)
        distance_if_reversed = N - distance_if_straight  # Если идём сквозь начало трассы
        distance = min(distance_if_straight, distance_if_reversed)
        current_cost += distance * supplies[destination_idx]
    if current_cost < min_cost:
        min_cost = current_cost

print(min_cost)

1. Открываем файл с помощью инструкции менеджера контекста with
2. Считываем количество километров N
3. Считываем количество необходимых продуктов питания на каждом километре с помощью генератора списков

5. Инициализируем нашу минимальную стоимость (которую мы будем каждую итерацию по возможности обновлять) очень большим числом (а именно бесконечностью)
6. Цикл по местоположению мобильного пункта питания (для каждого возможного положения пункта будем рассчитывать стоимость доставок)
7. Инициализируем стоимость доставки из этого пункта (на mobile_point_idx километре) нулём
8. Цикл по пункту назначения (вычисляем стоимость доставки необходимых продуктов для пункта destination_idx из пункта мобильного питания, находящегося на mobile_point_idx километре)
9. distance_if_straight - это расстояние, на которое нам нужно доставить, если мы будем двигаться в прямом направлении (не пересекая начало трассы)
10. distance_if_reversed - это расстояние, на которое нам нужно доставить, если мы будем двигаться в обратном направлении (через начало трассы)
11. Соответственно, то расстояние, которое проедет электрокар к этой точке, есть минимум этих двух расстояний
12. Стоимость доставки всех продуктов увеличиваем на стоимость доставки из пункта mobile_point_idx в пункт destination_idx
13. Цикл по пункту назначения закончился. Получили общую стоимость доставки. Если она меньше нашего текущего минимума,
14. то мы нашли новый минимум и записываем его в переменную

16. Перебрав все возможные значения пункта мобильного питания, печатаем минимальную стоимость. Это и есть наш ответ

Как проверять решение

Всегда когда вы написали какое-либо решение, проверяйте его. В этой задаче есть написанный пример с шестикилометровой трассой.

Создадим файл, например, D.txt с содержимым из примера, и запустим нашу программу (не забыв исправить в строке 1 A.txt на D.txt).

Ответ будет 96, как и объяснено в условии.

Это значит, что скорее всего, решение верное. Если сомневаетесь в своём решении, напишите вручную ещё несколько небольших примеров на задачу.

Для файла A.txt ответ будет 141530. Файл B.txt вычислить не получится: слишком долго.

Оптимизация решения

Что происходит при смещении точки мобильного питания?

Какие-то точки становятся на километр дальше, какие-то - на километр ближе.

А значит, можно быстро пересчитывать итоговую стоимость при сдвиге мобильного пункта. Напишем такое решение и подробно его разберём.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

with open("A.txt", "r") as f:
    N = int(f.readline().strip())
    supplies = [int(f.readline().strip()) for line in range(N)]

half_n = N // 2
current_cost = right_direction_sum = left_direction_sum = 0

for i in range(1, half_n + 1):
    current_cost += supplies[i] * i
    right_direction_sum += supplies[i]
for i in range(N - 1, half_n, -1):
    current_cost += supplies[i] * (N - i)
    left_direction_sum += supplies[i]
left_direction_sum += supplies[0]

total_costs = [current_cost]
for mobile_point_idx in range(1, N):
    total_costs.append(total_costs[-1] - right_direction_sum * 1 + left_direction_sum * 1)
    right_direction_sum = right_direction_sum - supplies[mobile_point_idx] + supplies[(mobile_point_idx + half_n) % N]
    left_direction_sum = left_direction_sum + supplies[mobile_point_idx] - supplies[(mobile_point_idx + half_n) % N]

print(min(total_costs))

6. Инициализируем переменные. current_cost - суммарная стоимость доставки для какого-то определённого положения мобильного пункта питания. right_direction_sum - суммарное количество обедов, которые электрокару выгоднее доставить, поехав в "правую" сторону (от километра с меньшим номером к километру с большим) left_direction_sum - суммарное количество обедов, которые электрокару выгоднее доставить, поехав в "левую" сторону
7. Теперь посчитаем эти переменные для случая, если мобильный пункт питания установлен на нулевом километре
8. Все километры с 1 по N // 2 включительно электрокару выгоднее доставить "направо"
9. Стоимость доставки в этот пункт supplies[i] * i (supplies[i] - количество комплектов питания, i - расстояние от 0 до точки доставки). Увеличиваем текущую стоимость
10. И увеличиваем right_direction_sum на количество обедов в этом пункте
11. Все километры с последнего по N // 2 электрокару выгоднее доставить "налево" (так как трасса кольцевая, то это маршрут 0 → N-1 → N-2 и т.д.)
12. Как и 9 строка, только расстояние равно N - i
13. И увеличиваем left_direction_sum на количество обедов в этом пункте
14. Условимся, что в сам пункт мобильного питания (сейчас это пункт 0) электрокар доставляет "налево" (пусть и проезжает нулевое расстояние). Увеличим left_direction_sum, а на стоимость доставки эта точка не влияет

16. Теперь создадим массив total_costs - это стоимость доставки, если пункт питания будет в точке, равной индексу массива. В точке 0, как мы посчитали, стоимость равна current_cost
17. Цикл по всем возможным позициям мобильного пункта
18. Считаем новую стоимость доставки. Она равна total_costs[-1] - стоимость доставки, если пункт питания находится на километр левее в сторону старта; - right_direction_sum * 1 - все обеды, которые выгодно доставлять направо, стали на 1 километр ближе (поскольку пункт питания сместился направо); + left_direction_sum * 1 - все обеды, которые выгодно доставлять налево, стали на 1 километр дальше
19. Но после перемещения пункта питания часть обедов стало выгоднее возить в другую сторону. Пункт mobile_point_idx мы доставляли "направо", теперь же и далее его будет выгодно доставлять "налево". А пункт (mobile_point_idx + half_n) % N мы доставляли "налево", теперь же и далее его будет выгодно доставлять "направо". Практический смысл пункта (mobile_point_idx + half_n) % N таков: это наиболее удалённая от пункта питания точка доставки. И при перемещении мобильного пункта правее, именно эта точка оказывается более выгодной для доставки "направо", чем "налево"
20. Соответственно, прибавляем и вычитаем количество обедов в соответствии с пунктом 19

22. В конце у нас получился массив со стоимостью доставок для каждого положения мобильного пункта. А ответом служит минимум из всех стоимостей

"Проверка" решения

У нас уже есть известные ответы для A.txt и D.txt. Запустим (не забыв поменять в строке 1 название файла) и проверим.

A.txt - 141530, D.txt - 96. Значит, скорее всего, решение верное.

Теперь запустим это решение на файле B.txt и получим ответ 18192010182272.

Вместо заключения

На самом деле, иногда эта программа выдаёт неправильный ответ. Приглашаю в нашу Telegram-группу обсудить, когда это решение выдаёт неправильный ответ, и как это решение исправить.

Заметка: на файлах A.txt, B.txt, D.txt решение и ответы правильные.