Задания
Версия для печати и копирования в MS Word
Тип 27 № 47231
i

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

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

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

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

Файл A

Файл B

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

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

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

6

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))

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ−2023 по ин­фор­ма­ти­ке
Спрятать решение · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026