Задание №26
Задание № 26
Тема: Умение обрабатывать целочисленную информацию с использованием сортировки. Время выполнения 35 минут.
ЕГЭ-2024
Задача 26 ЕГЭ-2024. Демо
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Ответ: 32 15
Объяснение решения 26 задачи ЕГЭ-2024. Демо
ЕГЭ-2023.
Решение задания № 26 ЕГЭ-2023. Демо. я.п. С/С++ и PascalABC.net
Условие задачи:
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д.
Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.
В файле (выше) приведено решение на двух языках программирования: С/С++ и PascalABC.net
Решение я.п. Python (задание 26 ЕГЭ-2023 Демо)
Ответ: 2767 | 51
приведем решение я.п. Python:
with open('26.txt','r') as fi:
n=int(fi.readline())
sp = [int(i) for i in fi]
sp.sort(reverse=True)
mx=sp[0]
cnt=1
for i in range(1,len(sp)):
if mx-sp[i]>=3:
cnt +=1
mx=sp[i]
print(cnt,mx)
Решение задач
Задача 1. (Ушаков Д.) внешний файл
Прораб обнаружил на складе некоторое количество (N) фрагментов ограждения. Из соображений эстетики он хочет положить эти фрагменты вдоль дороги длины M друг за другом так, чтобы каждый последующий фрагмент был длиннее предыдущего, и при этом увеличение длины каждого следующего фрагмента было бы минимальным из возможных. При этих условиях прораб хочет разложить ограждение вдоль наибольшей возможной длины дороги. Фрагменты ограждения стыкуются вплотную друг к другу. Резать фрагменты нельзя. Также нельзя, чтобы ограждение было длиннее дороги. Какова длина оставшейся без ограждения дороги? Какая наибольшая длина фрагмента, который использует прораб?
Входные данные.
В первой строке входного файла записаны два числа: число M — длина дороги в метрах (натуральное число, не превышающее 100 000) и число N — количество имеющихся фрагментов ограждения (натуральное число, не превышающее 10 000). В следующих N строках записано по одному числу — длина фрагмента ограждения в метрах (натуральное число от 10 до 400).
Запишите в ответе два числа: длину дороги (в метрах), которая останется без ограждения, и длину наибольшего фрагмента ограждения, который будет использован.
Пример входного файла:
400 9
100
170
80
50
240
150
40
150
80
При таких исходных данных одинаковые фрагменты дороги длины 80 и 150 не учитываем. Чтобы обеспечить условие строгого возрастания и самого меньшего возможного увеличения следующего фрагмента, рассмотрим варианты последовательного увеличения длины фрагментов. Возможные варианты, не превышающие 400:
40 + 50 + 80 + 100 = 270,
50 + 80 + 100 + 150 = 380,
80 + 100 + 150 = 330,
100 + 150 = 250, 150 + 170 = 320.
Из этих вариантов самый близкий к числу 400 — второй. Поэтому ответ для приведённого примера: 20; 150.
Ответ и решение
7 ; 383
with open('26-17.txt','r') as fi:
line=fi.readline().split()
m =int(line[0]) #длина дороги
n =int(line[1]) #кол-во фрагментов
#sp=[int(i) for i in fi]
sp=[]
for i in range(n):
c = int(fi.readline())
if c not in sp:
sp.append(c)
sp.sort()
s = 0
ogr =[]
i=0
while s<m:
s +=sp[i]
ogr.append(s)
i +=1
mm=ogr[-1]
mx=sp[i-1] #максимальный фрагмент ограды
i=0
if mm>m:
while mm>m:
mm -=sp[i]
i +=1
print(m-mm,mx)
Задача 2. (Ушаков Д.) внешний файл
Бюджетная теплоходная компания продаёт на свой теплоход больше билетов, чем в нём имеется посадочных мест, в надежде, что кто-нибудь передумает или не сможет поехать. Из-за особенностей ценообразования люди покупают билеты по различной цене. При посадке на теплоход мест хватает не всем. Чтобы минимизировать недовольство пассажиров и при этом получить наибольшую выгоду, компания поступает следующим образом: на теплоход сажает всех пассажиров с детьми, а из оставшихся пассажиров сажает тех, у кого цена билета выше, группы пассажиров не разбивает. Если можно посадить на теплоход всю группу, сажает всех. Если группа не помещается, её всю не сажает. Остальным выплачивает компенсацию, равную цене билета. Определите суммарную компенсацию, которую придётся выплатить компании, и наибольшую цену.
Входные данные
В первой строке входного файла записаны два числа: число M — количество мест на теплоходе (натуральное число, не превышающее 10 000), и число N — количество проданных групп билетов. В следующих N строках записано по 3 числа. Первое число — сумма продажи группы билетов (натуральное число, не превышающее 100 000), второе число — количество пассажиров в группе (натуральное число, не больше 10), третье число — есть ли в группе дети (1, если есть, 0, если детей нет). Считать, что средняя цена билета в группе всегда целое число.
Запишите в ответе два числа: суммарную компенсацию, которую должна будет выплатить компания всем пассажирам, которых не сможет перевезти, и наибольшую цену билета пассажира, которого не смогут перевезти.
Пример входного файла:
8 6
550 5 0
300 3 0
80 1 0
200 2 1
90 1 0
240 2 0
При таких исходных данных сначала посадим всех пассажиров с детьми. Это одна группа из двух пассажиров (200 2 1). Осталось 6 мест. Самые дорогие билеты по 120 у 2-х пассажиров. Их сажаем в первую очередь. Остаются 4 места.
Следующие по цене билеты у группы из 5-ти пассажиров. Их всех не сажаем, та как у нас осталось только 4 места. Из оставшихся выбираем пассажиров с самыми дорогими билетами: это 3 пассажира с билетами по 100. Их сажаем. Остаётся одно место. На него сажаем одного пассажира с билетом за 90. Пассажира с билетом за 80 не сажаем. Получается, суммарная компенсация: 550 + 80 = 630.
Наибольшая цена билета пассажира, которого не посадили — 110. Поэтому ответ для приведённого примера: 630; 110.
Ответ и решение
2354807; 2816
with open('26-16.txt','r') as fi:
line=fi.readline().split()
m = int(line[0])
n = int(line[1])
spd=[]
spg=[]
s_ost=[]
for i in range(n):
line=fi.readline().split()
a = int(line[0])
b = int(line[1])
c = int(line[2])
if c==1:
spd.append(b)
else:
spg.append([a,b])
s_d=m-sum(spd) #374
spg.sort(key=lambda i:i[0]//i[1],reverse=True)
i=0
s_k=0
mx=0
while i<len(spg):
if s_d>spg[i][1]:
s_d -=spg[i][1]
elif spg[i][1]!=1:
s_k +=spg[i][0]
mx = max(mx,spg[i][0]//spg[i][1])
elif spg[i][1]==1 and s_d!=0:
s_d -=1
elif s_d==0:
s_k +=spg[i][0]
i +=1
print(s_k,mx)
Задача 3. (Ушаков Д.) внешний файл
Комиссия по статистике решила изучить образ жизни среднестатистического торговца рыбой на рынке. Для этого собрала с каждого торговца информацию о том, сколько различных видов рыбы он продает и сколько при этом составляет средняя выручка торговца за месяц. Для выбора среднестатистического торговца комиссия решила отбросить всех торговцев, у которых количество продаваемых видов рыбы максимально и всех торговцев, у которых количество продаваемых видов рыбы минимально. Среди оставшихся торговцев комиссия решила отобрать тех, которые по уровню средней выручки за месяц находятся посередине. То есть, если посчитать количество оставшихся торговцев, имеющих доход выше «середнячков» и количество оставшихся торговцев, имеющих доход ниже «середнячков», то разница между этими количествами будет минимальной. Определите, сколько составляет средняя выручка за месяц такого среднестатистического торговца, и количество торговцев, которые соответствуют этому критерию. Считать, что существует ровно один вариант правильного ответа.
Входные данные
В первой строке входного файла находится число N — количество торговцев рыбой (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число — количество различных видов рыбы, которое продает торговец (натуральное число, не превышающее 100). Второе — средняя выручка торговца за месяц (натуральное число, не превышающее 109).
Запишите в ответе два числа: среднюю выручку среднестатистического торговца за месяц и количество среднестатистических торговцев.
Пример входного файла:
7
15 200
1 550
10 800
8 750
15 20
3 90
14 750
При таких исходных данных отбрасываем торговца с одним видом рыбы и двух торговцев с 15-ю видами рыбы. Остаются торговцы с выручкой 800, 750, 90 и 750. Среди них среднестатистических два (выручка по 750). Поэтому ответ для приведённого примера: 750; 2.
Ответ и решение
49620829; 8
with open('26-04.txt','r') as fi:
n = int(fi.readline())
mx=0
mn=101
sp=[]
for line in range(n):
line=fi.readline().split()
k=int(line[0])
sr_v=int(line[1])
mx=max(mx,k)
mn=min(mn,k)
sp.append([k,sr_v])
rez = []
for i in range(n):
if sp[i][0]!=mx and sp[i][0]!=mn:
rez.append(sp[i][1])
rez.sort(reverse=True)
s_v=round(sum(rez)/len(rez)) # среднее значение выручки
k_sr=0
k_msr=0
for i in range(len(rez)):
if rez[i]>s_v: k_sr +=1
if rez[i]<s_v:
k_msr +=1
k_st=abs(k_sr - k_msr) #кол-во рыботорговцев среднестатист. должно быть!
#находим среднестатист рыботорговцев
i=0
while rez[i]>s_v:
i +=1
rez_v=rez[i]
print(rez_v,rez.count(rez_v))
Задача 4. (Ушаков Д.) внешний файл
Придворному ювелиру поручили к празднику сделать как можно больше различных украшений. Ювелир умеет делать некоторое количество N различных украшений. На изготовление каждого украшения он тратит какое-то, заранее известное количество минут. При этом за самое дорогое украшение, которое ему удастся изготовить, ювелир получит премию, равную количеству потраченных минут. У ювелира имеется ограниченное количество времени M. При этом ювелир старается, сделав наибольшее возможное количество украшений, изготовить самое дорогое украшение, которое получится. Определите наибольшее количество украшений, которое сможет сделать ювелир, и наибольшее количество денег, которое он при этом сможет получить.
Входные данные
В первой строке входного файла записаны два числа: число M — количество минут, которое есть у ювелира (натуральное число, не превышающее 1 000 000) и число N — количество различных украшений, которое умеет делать ювелир (натуральное число, не превышающее 10 000). В следующих N строках записано по одному числу — количество минут, требуемых для изготовления одного украшения (натуральное число от 30 до 1000).
Запишите в ответе два числа. Наибольшее количество украшений, которое сможет изготовить ювелир, и наибольшее количество денег, которое он при этом сможет получить.
Пример входного файла:
500 7
240
150
50
120
80
190
40
При таких исходных данных ювелир сможет изготовить не более пяти украшений. Если изготовить все, кроме двух самых дорогих, останется еще 60 минут. Значит, можно вместо украшения за 150, сделать украшение за 190. Поэтому ответ для приведённого примера: 5; 190.
Ответы
3971; 489
Задание №26. Апробация 03022023. Вариант 1. внешний файл
На сборочном производстве штучных изделий хранятся комплекты N уплотнительных колец, которые согласно технологической карте сборки могут монтироваться одно внутри другого в необходимом количестве. Одно кольцо можно поместить в другое, если его диаметр хотя бы на 6 единиц меньше диаметра другого уплотнительного кольца. Определите наибольшее количество колец, которое можно использовать при сборке одного изделия, и максимально возможный диаметр самого маленького уплотнительного кольца.
Входные данные
В первой строке входного файла находится число N - количество уплотнительных колец (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров колец (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество колец, которое можно использовать для сборки, затем максимально возможный диаметр самого маленького кольца в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для набора из пяти уплотнительных колец и случая, когда минимальная допустимая разница между кольцами, подходящими для сборки изделия, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы колец с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество колец равно 3, а диаметр самого маленького кольца равен 32.
Ответы и решение
1575; 50
def f(i):
k = 1
ind=0
while i<l-1:
for j in range(i+1,l):
if sp[i]>=sp[j]+6:
k +=1
ind=j
break
i =j
return (k,sp[ind])
with open('26.txt','r') as fi:
n=int(fi.readline())
sp=[int(i) for i in fi]
sp.sort(reverse=True)
l=len(sp)
rez=f(0)
print(rez[0],rez[1])
Задачи по Демо-версии ЕГЭ 2024
Задача 1 (z26-v1kr) внешний файл
Входной файл содержит сведения о мероприятиях, в которых приглашён участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно или дистанционно). Определите, в каком максимальном количестве мероприятий может принять участие руководитель и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и длительность мероприятия. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Ответ:
26 20
Задача 2 (z26-v05kr) внешний файл
В тематическом парке для строительства арт-объектов используются однородные прямые круговые цилиндры с одинаковыми высотами; таких цилиндров заготовлено N штук. Руководством парка рабочим поставлена задача создать максимальной высоты пирамиду из поставленных друг на друга цилиндров, такую, чтобы каждый следующий цилиндр имел радиус основания не менее чем на 7 единиц меньше, чем предыдущий, чтобы у посетителей парка была возможность на образовавшиеся уступы помещать различные мелкие предметы. Определите количество цилиндров, которое нужно использовать для создания такой пирамиды, и максимально возможный радиус основания цилиндра, который будет находиться на вершине такой пирамиды.
Входные данные
В первой строке входного файла находится число N — количество цилиндров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин радиусов имеющихся цилиндров (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.
Запишите в ответе два целых числа: сначала количество цилиндров, которое необходимо использовать для строительства пирамиды максимальной высоты, затем максимально возможную длину радиуса цилиндра, который можно поместить на вершину такой пирамиды.
Ответ:
1196 2
Задача 3 (z26-v06kr) внешний файл
На прямолинейном участке пути для обеспечения связи необходимо разместить радио-передатчики. Установка каждого такого передатчика возможна на любом из N объектов, включённых в перечень разрешённых. Известно расстояние от нулевой отметки на этом участке до каждого объекта из данного перечня, кроме того по техническим нормативам для работы без помех два соседних передатчика должны находиться на расстоянии не менее 6 единиц друг от друга. На данном участке пути необходимо разместить максимальное количество передатчиков, не нарушая технические нормативы. Определите количество передатчиков при таком размещении и максимально возможное расстояние от нулевой отметки до ближайшего к ней передатчика.
Входные данные
В первой строке входного файла находится число N (натуральное число, не превышающее 10 000) — количество объектов, на которых можно устанавливать передатчики. В следующих N строках находятся значения расстояний от нулевой отметки до каждого из этих объектов (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.
Запишите в ответе два целых числа: сначала максимальное количество передатчиков, которое можно разметить на данном участке пути, не нарушая технические нормативы, затем максимально возможное расстояние от нулевой отметки до ближайшего к ней передатчика при таком размещении.
Ответ:
489 123
Задача 4 (z26-v09kr) внешний файл
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду). Для редактирования изображения Пете нужно изменить цвет с белого на чёрный всем имеющимся двум соседним белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наибольшим номером, в котором есть два соседних пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер пикселя в ряду из найденных в этом ряду подходящих пар белых пикселей.
Входные данные
В первой строке входного файла находится число N — количество рядов пикселей (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер чёрного пикселя в ряду.
Выходные данные
Два целых неотрицательных числа: номер ряда и наименьший номер пикселя в выбранной паре.
Ответ:
67890 98765
Решение заданий № 26 ЕГЭ прошлых лет
Основной алгоритм решения данной задачи - жадный алгоритм. Порядок решения - следующий:
Заполняем массив.
Сортируем его, например, по возрастанию.
Обращаем внимание на условие задачи: надо выполнить два условия - максимальный размер файла, который может быть помещен на диск, и, второе, - как можно больше "мелких" файлов в оставшееся дисковое пространство. Следовательно, берем (последовательно) максимальный по размеру файл и дополняем его остальными, начиная с самого маленького по размеру файла.
using namespace std;
int main(){ int s, n, c, mx, k, _mk=0, ind, l=0, sum; ifstream fi; fi.open("z26.txt"); ofstream fo; fo.open("out26.txt"); vector <int> rf; fi >> s >> n; for(int i=0;i<n;i++){ fi>>c; rf.push_back(c); } sort(rf.begin(),rf.end());//для 1000 пользователей возможен такой алгоритм ind = n - 1; sum = s; while(ind>0){ sum -=rf[ind]; int i=0; k=1; while(i<ind){ if(rf[i]<=sum){ k++; sum -=rf[i]; } ++i; } if(k>_mk){ _mk = k; mx = rf[ind]; } ind--; sum = s; } fo<< _mk << ' '<< mx <<endl; fi.close(); fo.close(); return 0;}
Решение на я.п. Pascal:
{$APPTYPE CONSOLE}uses SysUtils; var A: array[1..1000] of integer; i,s,n, mx,k,_mk,sum,j: Integer;procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; while L <= R do begin while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L + 1; R:= R - 1; end; end; QSort(first, R); QSort(L, last); end; end;
begin Assign(Input,'z26.txt'); Reset(input); Assign(Output,'out26ege21.txt'); Rewrite(output); read(s,n); for i:=1 to n do read(A[i]); Qsort(1,N); { сортировка } i:=n; sum:=s; _mk:=0; while i>1 do begin j:=1; k:=1; sum:=sum - A[i]; while j<i do begin if A[j]<=sum then begin sum:=sum-A[j]; k:=k + 1; end; j:=j+1; end; if k>_mk then begin _mk:=k; mx:=A[i]; end; i:=i-1; sum:=s; end; Writeln(_mk,' ',mx); Close(input); Close(output); end.