Задание №4597. Архив, необходимый для выполнения задания: ссылка для скачивания. Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна. Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе. Входные данные Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов питания на кольцевой трассе. В каждой из следующих N строк находится число – количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная с первого километра. В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B. Типовой пример организации данных во входном файле 6 8 20 5 13 7 19 При таких исходных данных, если пункты питания установлены на каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6. В этом случае сумма транспортных затрат составит: 1 ∙ 7 + 0 ∙ 19 + 1 ∙ 8 + 2 ∙ 20 + 3 ∙ 5 + 2 ∙ 13. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Задание №4597.
Создание собственной программы. ЕГЭ по информатике

Архив, необходимый для выполнения задания: ссылка для скачивания.

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

Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов питания на кольцевой трассе. В каждой из следующих N строк находится число – количество комплектов питания на пункте (все числа натуральные, количество комплектов питания на каждом пункте не превышает 1000). Числа указаны в порядке расположения пунктов питания спортсменов на трассе, начиная с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле
6
8
20
5
13
7
19

При таких исходных данных, если пункты питания установлены на каждом километре трассы, необходимо открыть мобильный цех подготовки комплектов питания для спортсменов в пункте 6.

В этом случае сумма транспортных затрат составит:

1 ∙ 7 + 0 ∙ 19 + 1 ∙ 8 + 2 ∙ 20 + 3 ∙ 5 + 2 ∙ 13.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Пояснение:
Для поиска искомой величины для файла А подойдет следующий алгоритм сложности O(n2), написанный на языке программирования Python.

filename = '1_27_A.txt' # Замените на '27-B.txt' для второго файла
with open(filename, 'r') as file:
    lines = file.readlines()
    
N = int(lines[0].strip())
kits = list(map(int, lines[1:N+1]))
    
# Вычисляем суммарную стоимость для каждой позиции
min_cost = float('inf')
for pos in range(N):
    total_cost = 0
    for i in range(N):
        distance = min(abs(i - pos), N - abs(i - pos))
        total_cost += kits[i] * distance
    if total_cost < min_cost:
        min_cost = total_cost
    
print(min_cost)

Для поиска искомой величины для файла B подойдет следующий алгоритм сложности O(n), написанный на языке программирования Python.

# Чтение данных из файла
filename = '1_27_B.txt' # Замените на '27-B.txt' для второго файла
with open(filename, 'r') as file:
    input = file.read().split()

ptr = 0
N = int(input[ptr])
ptr += 1
a = list(map(int, input[ptr:ptr+N]))
ptr += N
K = N // 2 ## середина массива

# Префиксные суммы для a, a[j]*j, a[j]*(N-j)
prefix_a = [0] * (N + 1) # кумулятивная сумма комплектов питания
prefix_aj = [0] * (N + 1) # кумулятивная сумма стоимости доставки питания
prefix_anj = [0] * (N + 1) # кумулятивная сумма обратной стоимости доставки питания

for i in range(1, N + 1):
    prefix_a[i] = prefix_a[i-1] + a[i-1]
    prefix_aj[i] = prefix_aj[i-1] + a[i-1] * (i-1)
    prefix_anj[i] = prefix_anj[i-1] + a[i-1] * (N - (i-1))

sum_total_anj = prefix_anj[N]
sum_a_total = prefix_a[N]

min_cost = float('inf')

for x in range(N):
    end = x + K
    if end <= N:
        sum_a_win = prefix_a[end] - prefix_a[x]
        sum_aj_win = prefix_aj[end] - prefix_aj[x]
        sum_anj_win = prefix_anj[end] - prefix_anj[x]
        sum_a_lt_x_win = 0
    else:
        end_wrapped = end - N
        sum_a_win = (prefix_a[N] - prefix_a[x]) + prefix_a[end_wrapped]
        sum_aj_win = (prefix_aj[N] - prefix_aj[x]) + prefix_aj[end_wrapped]
        sum_anj_win = (prefix_anj[N] - prefix_anj[x]) + prefix_anj[end_wrapped]
        sum_a_lt_x_win = prefix_a[end_wrapped]

    sum_rest_anj = sum_total_anj - sum_anj_win
    sum_rest_a = sum_a_total - sum_a_win
    sum_lt_x = prefix_a[x]
    sum_a_lt_x_rest = sum_lt_x - sum_a_lt_x_win

    term1 = sum_aj_win - x * sum_a_win + N * sum_a_lt_x_win
    term2 = sum_rest_anj + x * sum_rest_a - N * sum_a_lt_x_rest
    current_cost = term1 + term2

    if current_cost < min_cost:
        min_cost = current_cost

print(min_cost)

Объяснение.

1) Префиксные суммы. Массивы prefix_a, prefix_aj и prefix_anj хранят суммы элементов, их произведений на индексы и обратные расстояния соответственно.

2) Скользящее окно. Для каждого положения цеха x определяется окно длиной K (половина длины трассы). Суммы элементов в окне вычисляются с использованием префиксных сумм.

3) Цикличность трассы. При переходе через конец массива используется "заворачивание" индексов для корректного вычисления сумм.

4) Минимизация стоимости. Для каждого положения вычисляется суммарная стоимость и выбирается минимальная из них.

Показать ответ

Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке

Тест с похожими заданиями