Задание №27
ЕГЭ-2023. Задание № 27
Тема: Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей. Время выполнения 40 минут. (высокий уровень сложности).
Решение задания № 27 ЕГЭ-2023. Демо. В файле разобран алгоритм решения подобных задач и приведены коды решения задач на двух я.п.: С/С++ и PascalABC.net.
Решим эту задачу я.п. Python.
Условие задачи (чтобы не обращаться к файлу):
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).
Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
Добавим информацию из входных файлов: Файл А: количество записей – 100. Количество пунктов приема биоматериалов – 998.
Файл В: количество записей – 1100000. Количество пунктов приема: 9999994.
Если вы не сильны в реализации сложных алгоритмов, решите только первую часть задачи - для файла А. На Python это будет выглядеть так:
k=999
rp=[]
kk=[]
with open('27A.txt','r') as fi:
n=int(fi.readline())
for i in range(n):
p,bio=map(int,fi.readline().split())
rp.append(p)
q=ceil(bio/36)
kk.append(q)
mn=10**8
for x in range(n-1):
s=0
for y in range(n):
if y<x:
s +=(rp[x]-rp[y])*kk[y]
else:
s +=(rp[y]-rp[x])*kk[y]
mn=min(mn,s)
print(mn)
Ответ: 51063
Реализация алгоритма решения задачи (объяснен в файле) я.п. Python:
k=9999995
rp=[0]*k
kk=[0]*k
sm=0
with open('27B.txt','r') as fi:
n=int(fi.readline())
for i in range(n):
p,bio=map(int,fi.readline().split())
q=ceil(bio/36)
rp[p]=q
sm +=(p-1)*q #стоимость для 1 пункта
s=0
for i in range(1,k):
s +=rp[i]
kk[i]=s
mn=sm; sko=kk[-1]
for i in range(2,k):
sm = sm - (sko - kk[i-1]) + kk[i-1]
mn = min(mn,sm)
print(mn)
Ответ: 5634689219329
Этот код работает с двумя файлами: и А и В. Только не забывайте изменять значение переменной k.
Решение заданий № 27 ЕГЭ прежних лет
Данная задача осталась такой же, как и прежнем ЕГЭ. Задача на оптимизацию по времени выполнения программы и по памяти.
Напомню, оптимизация по памяти - не использовать массивы. Если данное условие выполнить невозможно, то размер массива должен быть как можно меньше.
Оптимизация по времени выполнения - выполнить задачу за один прогон.
Покажем на примере решения данной задачи.
Максимальная сумма может получиться, если из каждой пары выберем по одному числу - максимальному.
Если результат получился кратным 3 (что по условию задачи недопустимо), необходимо вычесть из результата какое-нибудь минимальное число. Под этим числом будем понимать не используемое в итоговой сумме число, которое есть в какой-нибудь паре и которое при делении на 3 не дает в остатке 0.
Итак, алгоритм решения задачи:
Читаем пары чисел один раз. Выбираем из пары максимальное число и добавляем в сумму.
Минимальное число проверяем на кратность 3. Если оно не кратно 3, то добавляем его в массив размерностью 3 ([0, 1, 2] - индексы элементов) с индексом мин_элемент mod 3, если этот элемент массива больше мин_элемента пары. То есть, заменяем существующее в массиве число.
Таким образом, к концу чтения пар, мы получим итоговую сумму и массив, содержащий, максимально, три числа (нам нужны только два - которые при делении на 3 дают в остатке 1 или 2). Окончательное решение задачи будет таким:
Если итоговая сумма кратна 3, то из двух чисел выбираем минимальное и вычитаем его из итоговой суммы, иначе - выводим значение итоговой суммы.
Особенность данного задания: надо найти ответ для двух файлов. Поэтому, все решение задачи размещается в подпрограмме, а в основном блоке программе - подключение внешних файлов - определение переменной типа string, в котором хранится имя подключаемого файла.
Решение на С++:
#include <bits/stdc++.h>using namespace std;long summa(string name){ long ost[3]={}; long n, a, b, d,i, mx, mn, sum=0; ifstream fi; fi.open(name); fi>>n; for(i=0;i<n;i++){ fi>> a>>b; if(a>b){ mx = a; mn = b; } else { mx = b; mn = a; } sum +=mx; d = mx-mn; if(ost[d%3]==0 ||ost[d%3]>d) ost[d%3] = d; } long _mn; for(int j=1;j<3;j++) if(ost[j]<_mn) _mn = ost[j]; if(sum%3==0) sum = sum - _mn;
return sum;}int main(){ long s1,s2; string name="27-A.txt"; s1 = summa(name); name = "27-B.txt"; s2 = summa(name); cout<<s1<<' '<<s2<<endl; return 0;}
Решение на я.п. Pascal:
{$APPTYPE CONSOLE}uses SysUtils;
var s1, s2: LongInt; name: string;function summa(name: string): LongInt;var n, a, b, d, i, mx, mn, sum, _mn, j: LongInt; ost: array[0..2] of LongInt;begin Assign(Input,name); Reset(input); for i:=0 to 2 do ost[i]:=0; read(n); sum:=0;_mn:=10001; for i:=1 to n do begin read(a,b); if a>b then begin mx:=a; mn:=b; end else begin mx:=b; mn:=a; end; sum:=sum + mx; d:=mx-mn; if (ost[d mod 3]=0) or (ost[d mod 3]>d) then ost[d mod 3]:=d; end; for j:=1 to 2 do if ost[j]<_mn then _mn:=ost[j]; Close(input); if sum mod 3 =0 then sum:=sum - _mn; summa:=sum; end;begin name:= '27-A.txt'; s1:=summa(name); name:='27-B.txt'; s2:=summa(name); Writeln(s1,' ',s2);end.