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

Задания

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

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

Файл A

Файл B

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

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

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

1 100

2 200

5 4

7 3

8 2

10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит:

1 · 2 + 3 · 1 + 5 · 1 + 6 · 1 + 8 · 2.

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

Решение. Сначала считаем общее количество пунктов. Далее построчно считаем все данные из файла в список elems, при этом сразу будем считать количество контейнеров, необходимое для перевозки пробирок в очередном пункте. Инициализируем список cost  — в нём будем хранить общую сумму транспортных затрат для размещения лаборатории в каждом из пунктов.

Сначала посчитаем общую стоимость затрат для первого в списке пункта. При в переменной rightSum посчитаем общее количество контейнеров пунктов справа, которые необходимо перевезти (аналогично в переменной leftSum будем считать общее количество контейнеров пунктов слева). Заметим, что чтобы посчитать общую стоимость затрат для следующего пункта, необходимо вычесть из общей суммы затрат предыдущего пункта значение переменной rightSum, умноженное на разницу расстояний текущего пункта и предыдущего. Также к получившемуся значению необходимо прибавить значение переменной leftSum, умноженное на разницу расстояний текущего пункта и предыдущего. При этом будем обновлять переменные leftSum и rightSum, прибавляя к первой количество контейнеров в предыдущем пункте и отнимая от второй количество контейнеров в текущем пункте.

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

from math import ceil

f = open("27_B.txt")

n = int(f.readline())

elems = []

sum = 0

rightSum = 0

leftSum = 0

for i in range(0, n):

a, b = map(int, f.readline().split())

elems.append([a, ceil(b / 36)])

cost = [0] * n

for i in range(1, n):

cost[0] += (elems[i][0] - elems[0][0]) * elems[i][1]

rightSum += elems[i][1]

for i in range(1, n):

leftSum += elems[i - 1][1]

cost[i] = cost[i - 1] - rightSum * (elems[i][0] - elems[i - 1][0]) + leftSum * (elems[i][0] - elems[i - 1][0])

rightSum -= elems[i][1]

print(min(cost))

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

Ответ: 51063 5634689219329.

Приведём решение Евгения Сахарова на языке Python.

f = open('27_B.txt')

n = int(f.readline())

v = 36

a = []

for i in range(n):

s, k = map(int, f.readline().split())

if k % v == 0:

c = k//v

else:

c = k//v + 1

a.append([s, c])

bags = [a[0][1]]

for i in range(1, n):

bags.append(bags[i - 1] + a[i][1])

for i in range(1,n):

bags[i] = bags[i-1] + a[i][1]

s = 0

for j in range(n):

s += abs(a[0][0] - a[j][0])*a[j][1]

min_sum = s

for i in range(1,n):

diff = a[i][0] - a[i-1][0]

s = s + diff*bags[i-1] - diff*(bags[n-1] - bags[i-1])

min_sum = min(min_sum, s)

print(min_sum)

Приведём решение Юрия Красильникова на языке Python.

punkt=[list(map(int,s.split())) for s in open('27_B.txt') ][1:]

for i in range(len(punkt)): punkt[i][1]=(punkt[i][1]-1)//36+1

spst=[sum([(p[0]-punkt[0][0])*p[1] for p in punkt])]

sumleft=punkt[0][1]

sumright=sum([x[1] for x in punkt[1:]])

for i in range(1,len(punkt)):

spst.append(spst[-1]+(sumleft-sumright)*(punkt[i][0]-punkt[i-1][0]))

sumleft+=punkt[i][1]

sumright-=punkt[i][1]

print(min(spst))

№ п/п	№ задания	Ответ
1	47231	51063 5634689219329

Ключ