Задание EGEINF64AB6F: Сортировка, отбор и моделирование

Решение.

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

В файле 972 продуктов, номера совпадают с порядком строк после заголовка. У каждого продукта две разные величины: срок хранения и срок после вскрытия. Все 2N чисел различны, поэтому при выборе минимального числа ничья не возникает.

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

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

Когда все продукты распределены, сохранённый номер относится к последнему размещённому продукту. Если его позиция с нуля равна p, выше стоят p продуктов, ниже — N − p − 1. Нужны более высокие места, поэтому берём p. Последовательность действий совпадает с алгоритмом условия. Время O(N log N), память O(N).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    values = []
    for number in range(1, n + 1):
        storage, opened = map(int, f.readline().split())
        values.append((storage, number, 0))
        values.append((opened, number, 1))
used = set()
left, right = 0, n - 1
for value, number, kind in sorted(values):
    if number in used:
        continue
    used.add(number)
    if kind == 0:
        position = left
        left += 1
    else:
        position = right
        right -= 1
    last_number, last_position = number, position
print(last_number, last_position)

Проверка результата.

Последним размещён продукт 9: определяющее значение срока 95109, вид — хранение. Его место в рейтинге при нумерации с единицы равно 465. Перед ним 464 продуктов, после него 507. Для данного условия выбираем первое из этих количеств.

Ответ: 9 464.