РЕШУ ЕГЭ — информатика

Задания

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

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

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

27_A.txt

27_B.txt

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

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

Типовой пример организации данных во входном файле:

При таких исходных данных, если контейнеры установлены на каждом километре автодороги, необходимо открыть центр переработки в пункте 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))

№ п/п	№ задания	Ответ
1	45261	471228 49113954961677

Ключ