На каждом 3-м километре кольцевой автодороги с двусторонним движением
Условие
На каждом 3-м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3N километров. Нулевой километр и 3N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общая стоимость доставки мусора из всех пунктов в этот центр была минимальной.
Определите минимальные расходы на доставку мусора в центр переработки отходов.
Входные данные.27_A.txt27_B.txtДано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) — количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число — количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B.Типовой пример организации данных во входном файле:6820513719При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 6. В этом случае сумма транспортных затрат составит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Приведём решение на языке Python. f = open("107_27_B.txt")n = int(f.readline())elems = [0 for i in range(n)]answers = [0 for i in range(n)]sum = 0rightSum = 0leftSum = 0for i in range(0, n): elems[i] = int(f.readline())for i in range(0, n): elems[i] = elems[i] * 3for i in range(1, n // 2): sum = sum + elems[i] * i + elems[n - i] * i rightSum = rightSum + elems[i] leftSum = leftSum + elems[n - i]sum = sum + elems[n // 2] * n // 2answers[0] = sumfor i in range(1, n): answers[i] = answers[i - 1] + leftSum + elems[i - 1] - rightSum - elems[(i + (n //
Осталось ещё 10 шагов
% n] rightSum = rightSum - elems[i] +…
% n] leftSum = leftSum - elems[(i + (n // 2))…
Приведём другое решение. Сначала считаем…
- 1 do begin sum := sum + elems[i] * i +…
mod n]; rightSum := rightSum - elems[i] +…
mod n]; leftSum := leftSum - elems[(i + (n…
Приведём решение Абдрахманова Леонида на…
+ elems[n - n // 2] * (n // 2)answers[0] =…
% n] rightSum = rightSum - elems[i] +…
% n] leftSum = leftSum - elems[(i - (n // 2))…
Бесплатно · займёт минуту