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

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

Опре­де­ли­те ми­ни­маль­ную сум­мар­ную сто­и­мость до­став­ки пи­та­ния для спортс­ме­нов из цеха его под­го­тов­ки в пунк­ты пи­та­ния на трас­се.

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

27_A.txt

27_B.txt

Дано два вход­ных файла (файл A и файл B), каж­дый из ко­то­рых в пер­вой стро­ке со­дер­жит число N (1 ≤ N ≤ 10 000 000)  — ко­ли­че­ство

пунк­тов пи­та­ния на коль­це­вой трас­се. В каж­дой из сле­ду­ю­щих N строк на­хо­дит­ся число  — ко­ли­че­ство ком­плек­тов пи­та­ния на пунк­те (все числа на­ту­раль­ные, ко­ли­че­ство ком­плек­тов пи­та­ния на каж­дом пунк­те не пре­вы­ша­ет 1000). Числа ука­за­ны в по­ряд­ке рас­по­ло­же­ния пунк­тов пи­та­ния спортс­ме­нов на трас­се, на­чи­ная с пер­во­го ки­ло­мет­ра.

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

6

8

20

5

13

7

19

При таких ис­ход­ных дан­ных, если кон­тей­не­ры уста­нов­ле­ны на каж­дом ки­ло­мет­ре ав­то­до­ро­ги, не­об­хо­ди­мо от­крыть центр пе­ре­ра­бот­ки в пунк­те 6. В этом слу­чае сумма транс­порт­ных за­трат со­ста­вит: 1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

Ти­по­вой при­мер имеет ил­лю­стра­тив­ный ха­рак­тер. Для вы­пол­не­ния за­да­ния ис­поль­зуй­те дан­ные из при­ла­га­е­мых фай­лов.

 

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

 

Ответ:

Спрятать решение

Ре­ше­ние.

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

 

Ре­ше­ние на языке Python.

f = open("1_27.txt")

n = int(f.readline())

elems = [int(i) for i in f]

answers = [0 for i in range(n)]

sum = 0

rightSum = leftSum = 0

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

 

Ответ: 141530, 18192010182272.

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


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