Задание 26 ЕГЭ: рейтинг: распределение по местам

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

Пример

Задание выполняется с использованием прилагаемого файла.

Для каждого из N смартфонов известны два числа: время работы в режиме ожидания и время работы в активном режиме (в минутах). По этим данным смартфонов распределяют по местам рейтинга — с 1-го по N-е.

Все 2N чисел упорядочивают по возрастанию и рассматривают по очереди, начиная с наименьшего. Если очередное число — время работы в режиме ожидания смартфона, который ещё не размещён в рейтинге, этот смартфон занимает первое свободное место с начала рейтинга. Если это время работы в активном режиме ещё не размещённого смартфона, смартфон занимает первое свободное место с конца рейтинга. Если смартфон уже размещён, число пропускается. Так продолжают, пока все смартфоны не будут размещены.

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

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

Первая строка входного файла 26.txt содержит натуральное число N — количество смартфонов. Каждая из следующих N строк содержит два натуральных числа: время работы в режиме ожидания и время работы в активном режиме очередного смартфона. Смартфоны пронумерованы начиная с 1 в том порядке, в котором они записаны в файле. Все 2N чисел в файле различны.

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

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

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

5
30 50
100 155
150 170
10 160
120 55

Числа рассматриваются в порядке 10, 30, 50, 55, 100, 120, 150, … Смартфон 4 (время работы в режиме ожидания 10) занимает 1-е место, смартфон 1 (30) — 2-е; число 50 пропускается, так как смартфон 1 уже размещён; смартфон 5 (время работы в активном режиме 55) занимает последнее, 5-е место; смартфон 2 (100) — 3-е; число 120 пропускается; смартфон 3 (150) — 4-е. Рейтинг: 4, 1, 2, 3, 5. Последним определено место смартфона 3, ниже него в рейтинге 1 смартфон. Ответ для примера: 3 1.

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

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Складываем все 2N чисел в один список вместе с номером объекта и признаком «первое/второе число», сортируем и моделируем процесс: два указателя — первое свободное место сверху и снизу. Уже размещённые объекты пропускаем. Последний размещённый объект занимает место, на котором встретились указатели; ниже него N − место объектов.

Ответ: 275 2059.

f = open("26.txt")
n = int(f.readline())
nums = []
for i in range(1, n + 1):
    a, b = map(int, f.readline().split())
    nums.append((a, i, 0))      # 0 — первое число: место сверху
    nums.append((b, i, 1))      # 1 — второе число: место снизу
nums.sort()

place = {}
top, bottom = 1, n
for v, i, kind in nums:
    if i in place:
        continue
    if kind == 0:
        place[i] = top
        top += 1
    else:
        place[i] = bottom
        bottom -= 1
    last = i
    if top > bottom:
        break
print(last, n - place[last])

Решить такую задачу — новый вариант с проверкой