Задача к ЕГЭ по информатике на тему «задачи под вебы» №2

Задача с ЕГЭ-2023

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

– все $2N$ чисел, обозначающих время окрашивания и шлифовки для $N$ деталей, упорядочивают по возрастанию;

– если минимальное число в этом упорядоченном списке – это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;

– если минимальное число – это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра

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

Этот алгоритм применяется последовательно для размещения всех $N$ деталей. Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые будут отшлифованы до неё.

Входные данные представлены в файле 26-129.txt следующим образом. Первая строка входного файла содержит натуральное число $N$ (1 $≤$ $N$ $≤$ 1000) – количество деталей. Следующие $N$ строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные). Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено её место на ленте транспортёра, затем количество деталей, которые будут отшлифованы до неё.

f = open(’26-129.txt’)
n = int(f.readline()) # Kоличество деталей
# Список времени шлифовки и времени окрашивания деталей
a = [list(map(int, i.split())) for i in f]
l = [] # Cписок для хранения времени, номера детали и типа обработки

for i in range(n): # Для каждой детали
    x, y = a[i] # x - время шлифовки, y - время окрашивания
    if x < y: # Если время шлифовки меньше времени окрашивания
# Записываем время шлифовки, номер детали и тип обработки
# (1 - шлифовка)
        l.append([x, i+1, 1])
    else:  # Если время окрашивания не больше времени шлифовки
# Записываем время окрашивания, номер детали и тип обработки
# (2 - окрашиваниe)
        l.append([y, i+1, 2])
l.sort() # Сортировка по времени
line1 = [] # Время шлифовки
line2 = [] # Время окрашивания

for i in l:
    if i[2] == 1: # Если деталь шлифуют
        line1.append(i) # Добавляем деталь в список для шлифовки
    else: # Если деталь красят
        line2.append(i) # Добавляем деталь в список для окрашивания

print(l[-1]) # Последняя размещенная на ленте деталь с номером 895
print(len(line1)-1) # Количество отшлифованных деталей ДО последней

Ответ: 895 488