Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по…

Задание #297700
Решено верно
Решено неверно
Сообщить о проблеме

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

В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:

  • все $2N$ чисел, обозначающих срок хранения и срок годности к употреблению для $N$ продуктов, упорядочивают по возрастанию;
  • если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
  • если минимальное число – это срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
  • если число обозначает срок хранения или годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.

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

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

В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) – количество продуктов. Следующие $N$ строк содержат пары чисел, обозначающих соответственно срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).

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

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

5
30 50
100 155
150 170
10 160
120 55

При таких исходных данных порядок расположения продуктов в рейтинге следующий: $4$, $1$, $2$, $3$, $5$. Последним займёт своё место в рейтинге продукт $3$. При этом три продукта займут более высокие места.

Это прямое моделирование описанного алгоритма. Собираем все $2N$ чисел, помечая каждое двумя вещами: номером продукта и типом — срок хранения или срок годности. Сортируем по возрастанию и идём по списку.

Для очередного числа смотрим, размещён ли уже его продукт. Если да, число пропускаем. Если нет, то при типе «срок хранения» продукт встаёт на первое свободное место с начала, а при типе «срок годности» — на первое свободное с конца. Достаточно держать два указателя: front растёт от единицы, back убывает от $N$.

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

f = open('26-09.txt')
n = int(f.readline())

nums = []
for i in range(1, n+1):
    a, b = map(int, f.readline().split())
    nums.append((a, i, 'A'))       # срок хранения
    nums.append((b, i, 'B'))       # срок годности
nums.sort()

placed = {}
front, back = 1, n
for _, i, t in nums:
    if i in placed:                # продукт уже размещён
        continue
    if t == 'A':
        placed[i] = front
        front += 1
    else:
        placed[i] = back
        back -= 1
    last, pos = i, placed[i]

print(last, pos - 1)   # 9 464

Проверка. Продуктов $972$, все они размещаются. Последним встаёт продукт номер $9$ со сроками $95109$ и $96164$ — его срок хранения оказался самым большим среди всех неразмещённых чисел. Он занимает позицию $465$, значит выше него стоят $464$ продукта. Предыдущие два шага заняли позиции $467$ и $466$ с конца, так что середина рейтинга сомкнулась ровно на нём. На типовом примере из условия программа выдаёт $3$ и $3$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение