Главная / ЕГЭ Информатика / Задание №27 / ID 34685
ID 34685 ЕГЭ Информатика Линия №27 СдамГИА ID: 45261 Анализ информационных моделей
✈️ TG ВК Следующая ⏭️
На каждом 3-⁠м километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 3N километров. Нулевой километр и 3N-⁠й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общая стоимость доставки мусора из всех пунктов в этот центр была минимальной.
Определите минимальные расходы на доставку мусора в центр переработки отходов.
Входные данные.

27_A.txt
27_B.txt

Дано два входных файла (файл 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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:
💡 Пошаговый разбор и решение:
Приведём решение на языке 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 = 0
rightSum = 0
leftSum = 0
for i in range(0, n):
elems[i] = int(f.readline())
for i in range(0, n):
elems[i] = elems[i] * 3
for 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 // 2
answers[0] = sum
for i in range(1, n):
answers[i] = answers[i - 1] + leftSum + elems[i - 1] - rightSum - elems[(i + (n // 2) - 1) % n]
rightSum = rightSum - elems[i] + elems[(i + (n // 2) - 1) % n]
leftSum = leftSum - elems[(i + (n // 2)) % n] + elems[i - 1]
print(min(answers))

Ответ: 471228, 49113954961677.

Приведём другое решение.
Сначала считаем количество чисел в файле, затем считаем все числа в массив elems. Поскольку контейнеры для мусора располагаются на каждом третьем километре автодороги, утроим каждый элемент массива. Далее для первого числа, считая его серединой, найдём сумму всех чисел справа от него (rightSum) и сумму всех чисел слева от него (leftSum) (учитываем, что дорога кольцевая, в примере из условия числа слева для числа 19  — это 5, 13 и 7, а числа справа  — это 8 и 20). Также при этом найдём общую стоимость доставки мусора при условии открытия центра переработки в первом пункте (элементе).
Заметим, что передвигая центр обработки в следующий пункт новая общая сумма будет равна сумме значения общей суммы центра обработки мусора в предыдущем пункте, значения переменной leftSum и значения элемента, в котором размещался центр обработки на предыдущей итерации, при этом из этого числа следует вычесть значение переменной rightSum и значение элемента, в который был передвинут центр обработки мусора. Также после передвижения центра обработки мусора будем обновлять значения переменных leftSum и rightSum. Все найденные подсуммы будем записывать в массив answers. Минимальное значение в получившемся в итоге массиве answers и будет ответом.

Приведём решение задачи на языке Pascal.

var
f: text;
n, i, sum, rightSum, leftSum: int64;
elems: array of int64;
answers: array of int64;
begin
assign(f, 'C:\27_B.txt');
reset(f);
readln(f, n);
setlength(elems, n);
setlength(answers, n);
sum := 0;
rightSum := 0;
leftSum := 0;
for i := 0 to n - 1 do readln(f, elems[i]);
for i := 0 to n - 1 do elems[i] := elems[i] * 3;
for i := 1 to (n div 2) - 1 do begin
sum := sum + elems[i] * i + elems[n - i] * i;
rightSum := rightSum + elems[i];
leftSum := leftSum + elems[n - i];
end;
sum := sum + elems[n div 2] * n div 2;
answers[0] := sum;
for i := 1 to n - 1 do begin
answers[i] := answers[i - 1] + leftSum + elems[i - 1] - rightSum - elems[(i + (n div 2) - 1) mod n];
rightSum := rightSum - elems[i] + elems[(i + (n div 2) - 1) mod n];
leftSum := leftSum - elems[(i + (n div 2)) mod n] + elems[i - 1];
end;
writeln(min(answers));
end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 471228, из файла B  — 49113954961677.

Приведём решение Абдрахманова Леонида на языке Python для N любой чётности.

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 = 0
rightSum = 0
leftSum = 0
for i in range(0, n):
elems[i] = int(f.readline())
for i in range(0, n):
elems[i] = elems[i] * 3
for i in range(1, n // 2):
sum = sum + elems[i] * i + elems[n - i] * i
rightSum = rightSum + elems[i]
leftSum = leftSum + elems[n - i]
if n % 2 == 0:
sum = sum + elems[n // 2] * (n // 2)
else:
sum = sum + elems[n // 2] * (n // 2) + elems[n - n // 2] * (n // 2)
answers[0] = sum
for i in range(1, n):
answers[i] = answers[i - 1] + leftSum + elems[i - 1] - rightSum - elems[(i + (n // 2) - 1) % n]
rightSum = rightSum - elems[i] + elems[(i + (n // 2) - 1) % n]
leftSum = leftSum - elems[(i - (n // 2)) % n] + elems[i - 1]
print(min(answers))
Правильный ответ: 471228&49113954961677
📚 Похожие разобранные задания по предмету:
ID 29584 • Задание №3
Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён...
Смотреть разбор ↗
ID 32278 • Задание №14
Значение выражения 497 + 721 − 7? записали в системе счисления с основанием 7. Сколько цифр 6 содержится в это...
Смотреть разбор ↗
🔗 Другие задания линии №27 по предмету Информатика:
ID 34669 Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой ... ID 34670 Последовательность натуральных чисел характеризуется числом Х  — наибольшим числом, кратным 14 ... ID 34671 На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются ... ID 34672 Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последо... ID 34673 На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары...
← Предыдущее задание 📚 Все задания по предмету Следующее задание →