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

На каж­дом 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))

 

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


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