вентилятор
Хорошего настроения!

ЕГЭ по информатике 2023 - Задание 26 (Сортировка)



Привет! В этой статье посмотрим некоторые задачи из 26 задания ЕГЭ по информатике.


Стоит отменить, что задачи из 26 задания являются одними из самых сложных во всем экзамене, и найти какой-то конкретный шаблон для всех типов задач не получится.


Но обычно в 26 задании нужно использовать сортирку.


Решать задачи будем преимущественно на языке Python.





Задача (Классическая, Демо 2021)

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.


Известно, какой объём занимает файл каждого пользователя.


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


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

В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.


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


Пример входного файла:

100  4
80
30
50
40

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:



250

Скачать файл


Решение:

Первый способ (с помощью Excel).


Решим задачу с помощью Excel. Чтобы открыть текстовый файл в программе Excel, выбираем Файл->Открыть, выбираем нужную папку и указываем, чтобы в папке были видны все типы файлов.


ЕГЭ по информатике демоверсия 2022 - задание 26 решение

И выбираем наш текстовый файл.


Выскочит окно Мастер текстов (импорт). Здесь оставляем выбранный пункт с разделителями и кликаем Далее.


В следующем окне поставим ещё галочку пробел. В итоге Символами-разделителем будут знак табуляции и пробел.


Кликаем ещё раз Далее и Готово.


Наши данные вставятся, как нужно!


ЕГЭ по информатике демоверсия 2022 - задание 26 решение 2

Число 8200 (размер свободного места) нужно запомнить или записать на черновике. Число 970 (количество файлов) нам в принципе не нужно при таком подходе решения.


Теперь удаляем первую строчку. Выделяем две ячейки в первой строчке, через контекстное меню мыши нажимаем Удалить.... Выбираем ячейки, со сдвигом вверх.





1. Найдём максимальное количество файлов.

Выделяем весь столбец A и сортируем его по возрастанию.


ЕГЭ по информатике демоверсия 2022 - задание 26 решение 3

Теперь выделяем ячейки сверху мышкой, а справа в нижней части программы будет показываться сумма выделенных ячеек.


ЕГЭ по информатике демоверсия 2022 - задание 26 сумма ячеек

Мы должны выделить максимальное количество ячеек, но чтобы сумма не превышала число 8200.


Получается максимальное количество файлов, которое можно сохранить, равно 568.





2. Найдём максимальный размер файла при максимальном количестве файлов.

Если мы сохраним максимальное количество файлов, то у нас ещё останется свободное место 8200-8176=24, т.к. сумма выделенных ячеек равна 8176.


Мы можем заменить наибольший файл (последняя выделенная ячейка равная 29) ещё большим файлом, размер которого не превышает 24+29=53.


Если покрутим таблицу вниз, то найдём такой файл размером 50. Это и будет наибольший файл при максимальном количестве файлов.


Ответ получается 568 50.


Второй способ (с помощью Python).


f=open('26.txt')
st = f.readline().split()
s=int(st[0])
n=int(st[1])

a=[]

#Записываем данные в список a
for i in range(n):
    x=int(f.readline())
    a.append(x)
    
#Сортируем список
a.sort()

b=[]

for i in range(n):
    if sum(b) + a[i] <= s:
        b.append(a[i])
    else:
        break

b=b[:-1]

for i in range(len(a)-1, -1, -1):
    if sum(b) + a[i] <= s:
        b.append(a[i])
        break

print(len(b), b[-1])




В начале подвязываемся к файлу. С помощью команды readline() считываем первую строчку. С помощью команды split() разбиваем строчку по пробелу на два числа. Переменная st - это список. В st[0] - будет подстрока с первым числом, в st[1] со вторым.


Переменная s - это размер свободного пространства на диске, n - это количество пользователей. Мы должны использоваться функцию int(), чтобы перевести из текстового типа данных в целый числовой.


Заводим пустой список a. В него мы будем помещать все значения объёмов пользователей, которые идут ниже по файлу. Зачитываем последующие числа в список a, превращая их в целый тип данных.


Команда .sort() сортирует (раскладывает по порядку) по возрастанию элементы списка.


Заводим список b. В него будем класть элементы, которые записываем на диск. Т.к. числа отсортированы, то, начиная с самого маленького файла, мы сможем заполнить диск максимальным количеством файлов.


С помощью цикла пробегаемся по всем элементам. В начале проверяем, есть ли место для очередного элемента, а потом записываем элемент в список b. Таким образом, сможем найти максимальное количество.


Чтобы найти максимальный элемент при максимальном количестве, удаляем из списка b последний самый большой элемент.


Пробегаемся по списку a, начиная с конца. Ищем кем можно заменить удалённый элемент. Мы идём с конца, поэтому в приоритете будут самый большие элементы.


После того, как найденный элемент будет умещаться в список b, можно печатать ответ.


Ответ:
56850




Задача (Двумерные списки)

В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.


По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 13 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 13 свободных мест.


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

В первой строке входного файла находится число N  — количество прижившихся саженцев сосны (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт деревце.


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

Два целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности из 13 мест, подходящих для посадки новых сосен.


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


7
40 3
40 7
60 33
50 125
50 129
50 68
50 72

Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.


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


Скачать файл




Решение:
f=open('26_dm.txt')

n=int(f.readline())

a=[0]*100001

for i in range(0, 100001):
    a[i]=[]


#Заполняем списки
for i in range(0, n):
    s=f.readline()
    b=s.split()
    a[int(b[0])].append(int(b[1]))


#Сортируем списки
for i in range(0, len(a)):
    a[i].sort()


flag_stop=0

for i in range(len(a)-1, -1, -1):
    for j in range(0, len(a[i])-1):
        if a[i][j+1]-a[i][j]==14:
            print(i, a[i][j]+1)
            flag_stop=1
            break

    if flag_stop==1:
        break 




Всего у нас может быть сто тысяч рядов. Поэтому мы заводим 100000 списков. Каждый список - это очередной ряд. Но в программе завели 1000001, т.к. нулевой список использоваться не будет.


ЕГЭ по информатике демоверсия 2023 - задание 26 (двумерный список)

В каждый ряд добавляются номера деревьев. Это и будут элементы для каждого списка. Если не будет деревьев в ряду, то список останется пустым.


В программе мы сортируем каждый список, чтобы числа все шли в порядке возрастания.


Если в каком-нибудь списке числа имеют разницу в 14 единиц, то значит между ними ровно 13 свободных мест. Например, числа 10 и 24. Между ними 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23. Всего 13 чисел.


Чтобы проанализировать двумерный массив, используем вложенные циклы. Ряды перебираем сверху вниз. Как только найдём нужный ряд, выйдем из цикла, и в переменной i будет наибольший нужный ряд.


Сами же ряды перебираем в порядке возрастания. Как только между числами разница будет в 14 единиц, то значение j+1 наименьший свободный номер из промежутка в 13 деревьев.


Чтобы вовремя выйти из вложенных циклов, используем дополнительный флаг (переменную flag_stop).


Ответ:
5996650449




Задача (Демо 2023)

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробоку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.


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

В первой строке входного файла находится число N - количество коробок в магазине (натуральное число, не превышающая 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке.

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


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


5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих упаковки "матрёшки", составлят 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.


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


Скачать файл


Решение:
f=open('26.txt')
n=int(f.readline())

a=[]

for i in range(n):
    x=int(f.readline())
    a.append(x)


a.sort(reverse=True)

k=1
p=a[0]

for i in range(1, len(a)):
    if p-a[i]>=3:
        k=k+1
        p=a[i]

print(k, p)

В начале считываем все числа в массив (список) a. Сортируем их в порядке убывания.


Приступаем собирать упаковку. Начинаем с самой большой упаковки. Большую упаковку точно можно взять в наш подарок. Переменная p - это размер последний коробки, которую мы взяли. Переменная k - количество коробок в подарке на текущий момент времени.


Если следующая коробка подходит по условию, то мы её берём в наш подарок. Кто-то может подумать, что, может быть, выгоднее взять не самую большую коробку, а предпоследнего размера. Но все размеры, которые будут подходить для предпоследнего элемента, точно будут подходить и для последнего, и количество упаковок точно не будет меньше, если мы берём самую большую коробку.


Дубликаты не влияют на ответы.


Если мы начинаем с самой большой коробки, то в самом конце в переменной p окажется максимальный размер самой маленькой коробки.


Ответ:
2767 51




Задача (Разные типы товаров)

На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа A. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.


Определите, сколько будет закуплено товаров типа A и сколько денег останется.


Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество товаров и M – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

Запишите в ответе два числа: сначала количество закупленных товаров типа A, затем оставшуюся неиспользованной сумму денег.


Пример входного файла:


6 110
40 E
50 A
50 D
30 C
20 B
10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа A. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 A). Останется 0 рублей. Ответ: 2 0.


Скачать файл




Решение:
f=open('26-rtt.txt')

s=f.readline().split()
n=int(s[0])
m=int(s[1])

X, Y, Z = [], [], []

for i in range(n):
    s=f.readline().split()
    X.append((int(s[0]), s[1]))

X.sort()

sm=0

for i in range(n):
    if sm+X[i][0]<= m:
        sm=sm+X[i][0]
        Y.append(X[i])
    else:
        if X[i][1]=='A':
            Z.append(X[i])


j=0
for i in range(len(Y)-1, -1, -1):

    if Y[i][1]=='A': continue
    
    if sm - Y[i][0] + Z[j][0] <= m:
        sm = sm - Y[i][0] + Z[j][0]
        Y[i] = Z[j]
    else:
        break

    j=j+1

count = 0
for i in range(len(Y)):
    if Y[i][1]=='A':
        count=count+1

print(count, m-sm)

В этом решении участвуют три списка. Список X - это все товары из нашего файла. Каждый товар - это отдельный список, состоящий из двух элементов: стоимости и типа товара.


После того, как список X укомплектован, сортируем его по первому значению (по цене). Таким образом, самые дешёвые товары всех типов будут находится в начале, самые в дорогие в конце. Так мы сможем найти максимальное количество, которое можно закупить на указанную сумму.


Список Y - это те товары, которые мы взяли при вычислении предыдущего шага. Переменная sm - это та сумма, которую потратим при нахождении максимального количества товаров в независимости от типа товаров.


Список Z - это те товары, которые мы НЕ взяли в предыдущем шаге, но только с типами A.


Основной секрет данной задачи заключается в том, что мы будем убирать по очереди один элемент из списка уже взятых товаров типа В и добавлять один товар типа A из списка не взятых товаров. Т.к. мы всегда один элемент убираем и один прибавляем, то количество остаётся одинаковым, т.е. максимальным. Тем самым мы стараемся сделать товаров типа A как можно больше.


Нужна максимальная экономия при заменах, чтобы можно было сделать как можно больше замен, и при это осталось как можно больше денег. Для этого всегда меняем самый большой элемент из списка Y, на самый маленький элемент из списка Z

При заменах меняем и значение суммы выбранных элементов (переменная sm).

Когда замены больше невозможны, то остаётся только посчитать количество элементов с типом A в списке Y.


Ответ:
35 44




Задача (Интересный шаблон)

Предприятие производит оптовую закупку изделий A и C, на которую выделена определённая сумма денег. У поставщика есть в наличии партии этих изделий различных модификаций по различной цене. На выделенные деньги необходимо приобрести как можно больше изделий C (независимо от модификации). Закупать можно любую часть каждой партии. Если у поставщика закончатся изделия C, то на оставшиеся деньги необходимо приобрести как можно больше изделий A. Известна выделенная для закупки сумма, а также количество и цена различных модификаций данных изделий у поставщика. Необходимо определить, сколько будет закуплено изделий A и какая сумма останется неиспользованной. Если возможно несколько вариантов решения (с одинаковым количеством закупленных изделий A), нужно выбрать вариант, при котором оставшаяся сумма максимальна.


Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество партий изделий у поставщика и S – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк описывает одну партию изделия: сначала записана буква A или C (тип изделия), а затем – два целых числа: цена одного изделия в рублях и количество изделий в партии. Все данные в строках входного файла разделены одним пробелом.


В ответе запишите два целых числа: сначала количество закупленных изделий типа A, затем оставшуюся неиспользованной сумму денег.


Пример входного файла:
4 1000
A 14 12
C 30 7
A 40 24
C 50 15

В данном случае сначала нужно купить изделия C: 7 изделий по 30 рублей и 15 изделий по 50 рублей. На это будет потрачено 960 рублей. На оставшиеся 40 рублей можно купить 2 изделия A по 14 рублей. Таким образом, всего будет куплено 2 изделия A и останется 12 рублей. В ответе надо записать числа 2 и 12.


Скачать файл


Решение:

Создадим список. Каждый элемент списка будет является тоже списком из трёх элементов: тип изделия, цена изделия и количество изделий данной модификации.


Нам потребуется отсортировать строчки файла сначала по типу изделия, т.к. нужно приобрести как можно больше изделий типа C. После этого нужно сделать сортировку второго уровня, отсортировать строчки по цене. Ведь так мы сможем взять максимальное количество изделий на выделенную сумму.


Рассмотрим интересный шаблон для подобного рода задач.


a=[]
a.append((5, 1, 6))
a.append((7, 7, 3))
a.append((3, 4, 5))
a.append((3, 1, 2))
a.append((3, 3, 2))

a.sort(key=lambda d: (d[0], d[1]))
print(a)




Получается результат:


Результат многоуровневой сортировки

Видим, что сначала элементы расположились по первому числу, затем уже по второму.


Напишем решение для нашей задачи.


f=open('26_4.txt')
st=f.readline().split()

n=int(st[0])
s=int(st[1])

k=0

a=[]

for i in range(n):
    st=f.readline().split()
    if st[0]=='A': st[0]='D'
    if st[0]=='C': st[0]='B'
    a.append((st[0], int(st[1]), int(st[2])))


a.sort(key=lambda d:(d[0], d[1]))

for i in range(len(a)):
    for j in range(a[i][2]):
        if s-a[i][1]>=0:
            s=s-a[i][1]
            if a[i][0] == 'D':
                k=k+1

print(k, s)

Т.к. нужно в начале набрать изделий типа С как можно больше, то хотелось бы видеть именно в начале этот тип после сортировки. Чтобы добиться желаемого, обозначим букву С за букву B, а букву A за D. Сортировку по цене делаем в возрастающем порядке.


Далее пробегаемся в цикле по отсортированному списку. Во вложенном цикле покупаем один товар конкретной модификации, пока это можно сделать. Посчитываем количество товаров типа A.


Ответ:
7354 111




Задача (Бинарный поиск)

В текстовом файле записан набор натуральных чисел, не превышающих 109. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.


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

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.


В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.


Пример входного файла:
6
3
8
14
11
2
17

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 11.


Скачать файл

Решение:
f=open('26_6.txt')
n=int(f.readline())

k=0
mx=0
a=[]

for i in range(n):
    x=int(f.readline())
    a.append(x)

a.sort()

for i in range(0, len(a)-1):
    if a[i]%2==0:
        for j in range(i+1, len(a)):
            if a[j]%2==0:

                sr = (a[i] + a[j]) // 2

                # Бинарный поиск
                l=0
                r=len(a)-1
                index=0

                while(l <= r):
                    
                    index = (r + l) // 2

                    if a[index] == sr:
                        k=k+1
                        mx=max(mx, a[index])
                        break
                    if a[index] < sr:
                        l=index+1
                    else:
                        r=index-1

print(k, mx)

В начале записываем все числа в массив. Сортируем все числа, как обычно в 26 задании из ЕГЭ по информатике.


После идут два вложенных цикла - мы перебираем все пары в массиве a. Берём только чётные числа.


Чтобы найти число в отсортированном массиве воспользуемся "бинарным поиском". Об этом приёме подробно рассказано в этой статье.


Ответ:
15 976339247




Задача (ЕГЭ по информатике 2023, расписание мероприятий)

Входной файл содержит сведения о заявках на проведения мероприятий. В заявках даны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба.


Определите, какое максимальное количество мероприятий можно провести, и самое позднее время окончания последнего мероприятия (в минутах).


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

В первой строке входного файла находится натуральное число N (N < 1000) - количество заявок.


Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Числа натуральные, не превышающие 1440.


В ответ дайте два числа: максимальное количество мероприятий и самое позднее время окончания последнего мероприятия (в минутах).


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


5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5.


Самое позднее время окончания последнего мероприятия будет равно 180 минутам, если состоятся мероприятия по заявкам 2, 4, 5.


Скачать файл

Решение:

f=open('26_2023_1.txt')
n=int(f.readline())
a=[]
for i in range(n):
    st = f.readline().split()
    a.append((int(st[0]), int(st[1])))

# Сортируем по второму элементу
a.sort(key=lambda x: x[1])

gr=0
gr2=0
k=0

mx_end = 0

# Ищем максимальное количество
for i in range(n):
    if a[i][0] >= gr:
        gr2=gr # Окончание предпоследнего выбранного элемента
        gr=a[i][1]
        k=k+1
        
# Ищем максимальное время последнего элемента при максимальном количестве
for i in range(n):
    if a[i][0] >= gr2:
        mx_end=max(mx_end, a[i][1])

print(k, mx_end)

Чтобы найти максимальное количество мероприятий, сортируем все мероприятия по времени окончания. Начинаем подбирать мероприятия с самым маленьким временем окончания.


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


При таком подходе мы сможем найти максимальное количество мероприятий.


Чтобы найти максимальное время окончания последнего мероприятия при максимальном количестве, мы должны запомнить время окончания предпоследнего взятого мероприятия. За это отвечает переменная gr2.


Кандидатов для последнего мероприятия может быть несколько, но мы должны взять то, у которого время окончание будет самое большое.


Ответ:
49 1430




Задача (ЕГЭ по информатике 2023, конвейер деталей)

На производстве штучных изделий имеется N деталей, которые требуют шлифовки и окрашивания. У каждой детали известны временные затраты на шлифовку и окрашивание. Детали пронумерованы, начиная с единицы.


В процессе обработки деталей не предусмотрена возможность параллельной работы.


На транспортной ленте имеется N мест для каждой детали.


На транспортной ленте детали располагаются по следующему правилу:


1) Для N деталей имеется 2N чисел, которые обозначают время окрашивания и время шлифовки каждой детали. Эти 2N чисел сортируются по возрастанию.


2) Если минимальное число в упорядоченном списке представляет время шлифовки конкретной детали, то данную деталь размещают на транспортной ленте на первое свободное место, начиная от её начала.


3) Если минимальное число в упорядоченном списке представляет время окрашивания конкретной детали, то данную деталь размещают на транспортной ленте на первое свободное место, начиная от её конца.


Если попадается число уже рассмотренной детали, то его игнорируют.


Все N деталей последовательно размещаются на транспортной ленте с помощью данного алгоритма.


Определите номер последней детали, для которой будет определено её место на транспортной ленте, и количество деталей, которые будут отшлифованы до неё.


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


В первой строке входного файла находится натуральное число N (N < 1000), которое обозначает количество деталей.


Следующие N строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания каждой детали. Все числа являются натуральными и различными.


Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено место на транспортной ленте, затем количество деталей, которые будут отшлифованы до неё.


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


5
30 50
100 155
150 170
10 160
120 55

При таком входном файле расположение деталей на транспортной ленте будет следующим: 4, 1, 2, 3, 5. Последней займёт своё место на ленте деталь под номером 3. До неё будет отшлифовано 3 детали.


Скачать файл

Решение:

f=open('26_2023_2.txt')
n=int(f.readline())
a=[] # Список шлифовки
b=[] # Список окрашивания
c=[] # Список использованных деталей
for i in range(1, n+1):
    st = f.readline().split()
    a.append((int(st[0]), i))
    b.append((int(st[1]), i))

a.sort()
b.sort()

u1=0
u2=0

k=0

end_el = 0 

for i in range(2*n):
    if a[u1][0] < b[u2][0]:
        if not(a[u1][1] in c):
            c.append(a[u1][1])
            k=k+1
            end_el=1
        if u1 < n - 1:
            u1 = u1 + 1
    else:
        if not(b[u2][1] in c):
            c.append(b[u2][1])
            end_el=0
        if u2 < n - 1:
            u2 = u2 + 1
print(c[-1], k-end_el)

В список a будем класть время шлифовки детали, а так же к каждому числу добавляем номер детали.


В список b будем класть время окраски детали, а тоже к каждому числу добавляем номер детали.


В список c будем добавлять номера деталей, которые мы разместили на транспортной ленте.


Сортируем списки a и b.


Переменные u1 и u2 - это указатели для списков a и b. Мы берём самые маленькие элементы из этих списков и сравниваем между собой. Тот элемент, которые меньше, идёт на транспортную ленту. Указатель того списка, из которого деталь была перенесена на транспортную ленту, увеличивается на 1. Если указатель дошёл до верхней границы n - 1, то он перестаёт увеличиваться.


Мы добавляем номер детали в список c тогда, когда этого номера ещё нет в этом списке.


Основной цикл повторяется 2*N раз, чтобы проанализировать каждое число.


Если мы добавляем в список c деталь для шлифовки, то прибавляем счётчик k на 1. Переменная end_el запоминает, куда пошла последняя деталь. Если она пошла на шлифовку, то переменная end_el будет равна 1. Если оа пошла на окраску, то она будет равна 0.


Таким образом, мы найдёт количество отшлифованных деталей до того момента, когда мы положили на транспортную ленту последнюю деталь. Оно равно k-end_el.


Номер последней детали находится из списка c (с[-1]).


Информация о том, что детали для шлифовки кладут от начала ленты, а для окраски от конца, в данной задачи не пригодилась.





Можно переписать программу, где будет использоваться только один список a, где будут размещаться и время шлифовки, и время окрашивания.


f=open('26_2023_2.txt')
n=int(f.readline())
a=[] # Список шлифовки и окрашивания
c=[] # Список использованных деталей
for i in range(1, n+1):
    st = f.readline().split()
    a.append((int(st[0]), 0, i))
    a.append((int(st[1]), 1, i))

a.sort()

k=0

end_el = 0 

for i in range(2*n):

    if not(a[i][2] in c):
        c.append(a[i][2])
        if a[i][1]==0:
            k=k+1
            end_el=1
        else:
            end_el=0

print(c[-1], k-end_el)

Когда мы добавляем в список a время детали, второй параметр отвечает за шлифовку или окрашивание. Если добавляем время шлифовки, то этот параметр равен 0, если время окрашивания, то 1.


Ответ:
186 521




Задача (ЕГЭ по информатике 2023, посетители магазина)

Система наблюдения регистрирует каждый вход и выход покупателей в режиме реального времени в минутах, прошедших от начала суток. Магазин работает 24 часа от начала суток без перерыва.


Данные анализируются за прошедшие сутки.


Найдите максимальное количество посетителей, которое находилось в магазине одновременно. Найдите сколько было временных отрезков, в которых было максимальное количество посетителей.


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


В первой строке входного файла находится натуральное число N (N < 10000) - количество посетителей магазина.


Следующие n строк содержат пары чисел, обозначающих соответственно время входа и время выхода посетителя (все числа натуральные и не превышают 1440).


Запишите в ответе два натуральных числа: сначала найденное количество временных отрезков, где будет максимальное количество посетителей, а затем максимальное число посетителей, которое будет находится в магазине одновременно.


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


6
10 50
100 150
110 155
120 160
130 170
151 170

При таких исходных данных было два временных отрезка, где было максимальное количество посетителей. Со 130 минуты по 150 минуты и со 151 минуты по 155 минуты. Максимальное количество посетителей в эти временные отрезки равно 4.


Скачать файл

Решение:

Найдём в начале максимальное количество посетителей в магазине.


f=open('26_2023_3.txt')

n=int(f.readline())

k=0
kmax=0
a=[]
for i in range(n):
    st = f.readline().split()
    a.append((int(st[0]), int(st[1])))

for i in range(1441):

    for el in a:
        if el[0]==i:
            k=k+1
            
        if el[1]==i:
            k=k-1

    kmax=max(kmax, k)
        
print(kmax)

Получается максимальное число в магазине 3535. Здесь мы заносим время входа и выхода каждого посетителя в массив a.


Затем анализируем каждую минуту суток, начиная с нуля. Внутри основного цикла пробегаемся по списку a (по всем посетителям). Если кто-то вошёл в эту минуту, то мы прибавляем 1 к счётчику k, если кто-то вышел, значит, отнимаем 1 от счётчика k. Таким образом, мы всегда будем знать количество посетителей в магазине в данную минуту. Применяем приём "царь горы", чтобы отследить максимальное значение.


Здесь используются вложенные циклы, но т.к. значение в 26 задании небольшие, программа найдёт ответ за разумное время.


Найдём количество временных отрезков, когда было посетителей в магазине максимальное количество (3535).


f=open('26_2023_3.txt')

n=int(f.readline())

k=0
kmax=0
a=[]
for i in range(n):
    st = f.readline().split()
    a.append((int(st[0]), int(st[1])))

count=0
for i in range(1441):

    last_k=k

    for el in a:
        if el[0]==i:
            k=k+1
            
        if el[1]==i:
            k=k-1

    if k==3535  and last_k < 3535:
        count=count+1

    kmax=max(kmax, k)
        
print(count, kmax)

До того как мы обсчитали конкретную минуту, мы сохраняем значение k в переменную last_k. Нас интересует именно переход last_k<3535 к значению k=3535. Это и будет временной отрезок с максимальным количеством посетителей.


Важно засчитывать именно переход до максимального значения, а не подсчитывать минуты, когда значение k максимально.


Эта задача интересна тем, чтоб здесь не используется сортировка.





Приведём более эффективное решение.


В предыдущем решении плохо было то, что мы получили вложенные циклы. При увеличении объёма входных данных, программа может медленно работать. Попробуем исправить это.


f=open('26_2023_3.txt')

n=int(f.readline())

b=[0]*1441

k=0
kmax=0
for i in range(n):
    st = f.readline().split()
    b[int(st[0])] += 1
    b[int(st[1])] -= 1

k=0
kmax=0
for i in range(1441):
    k=k+b[i]

    kmax=max(kmax, k)
        
print(kmax)

Так мы находим максимальное количество посетителей. Получается 3535.


Здесь мы заводим список b. Каждая ячейка этого списка отвечает за свою минуту. Получается, мы заводим мини-счётчики для каждой минуты. Если человек вошёл в магазин на данной минуте, мы соответствующий счётчик увеличиваем на 1. Если человек вышёл, то уменьшаем счётчик для этой минуты на 1.


Таким образом, мы получаем баланс для каждой минуты. Это значение может быть и отрицательным. К примеру, на какой-то минуте три человека вышло, но ни одного не зашло.


В основном цикле мы просто прибавляем баланс каждой минуты для главного счётчика k.


f=open('26_2023_3.txt')

n=int(f.readline())

b=[0]*1441

k=0
kmax=0
for i in range(n):
    st = f.readline().split()
    b[int(st[0])] += 1
    b[int(st[1])] -= 1

k=0
kmax=0
last_k=0
count=0
for i in range(1441):
    last_k=k
    
    k=k+b[i]
    
    if k==3535 and last_k<3535:
        count=count+1
    
    kmax=max(kmax, k)
        
print(count, kmax)

Количество временных отрезков с максимальным числом посетителей ищем так же, как и в прошлом решении.


В этом решении мы избавились от вложенных циклов и сделали его более эффективным.


Ответ:
4 3535


Надеюсь, Вам повезёт при решении 26 задания на ЕГЭ по информатике.






16-01-2023 в 14:00:23





Поддержать сайт:


Похожая статья:

ОГЭ по информатике. Вторая часть. Определение количество элементов - задачи на Паскаль (Pascal)

Решение задач на паскаль из второй части ОГЭ по информатике. Определен...

Категория: Информатика  Подкатегория: ОГЭ
Дата: 28-09-2018 в 14:05:11 0


Комментарии:

Александр, будут ли разборы задач с чередующимися красными и синими коробками(как в 4 варианте сборника Крылова и Чуркиной)? Писал в школе пробник по этому варианту, и набрал 95 баллов, спасибо вам за отличные уроки, это очень эффективная подготовка
Артём 14-02-2023 в 17:55:36

Спасибо за отзыв!) Посмотрю эту задачку, если что, разберу.
Калужский Александр 14-02-2023 в 18:03:49

Александр, полагаю, у вас опечатка в задаче с "Интересным шаблоном". Последняя строчка решения: "Посчитываем количество товаров типа С." - В задаче говориться о типах А.
Михаил 19-02-2023 в 10:14:38

Спасибо, исправил!
Калужский Александр 19-02-2023 в 12:29:59



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.