Данные из файла нужно отсортировать и обработать жадным алгоритмом: рейтинг продуктов, архив файлов, свободные места в зале. Ответ — два числа. К каждому варианту — файл.
Общий подход
Прочитать файл, сложить данные в список кортежей.
Отсортировать так, чтобы задача решалась одним проходом (жадно).
Проверить алгоритм на примере из условия.
Приёмы
Сортировка кортежей: сначала по первому элементу, потом по второму.
Соседние элементы: zip(a, a[1:]).
Ответ из двух чисел: print(x, y).
Типичные ошибки
Перепутать порядок чисел в ответе.
Во втором числе ответа забыть про условие на первое.
Читать первую строку файла как данные.
Разобранные варианты
Сначала напиши программу сам и проверь её на примере, потом открой разбор.
Вариант 1
рейтинг продуктов
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Идея. Для каждого продукта важно только меньшее из двух чисел: продукт размещается, когда до него дойдёт очередь по возрастанию, то есть по своему минимальному числу. Если меньшее — срок хранения, продукт встаёт в начало (на первое свободное место), иначе — в конец.
Алгоритм. Сортируем продукты по минимальному числу, раскладываем по двум спискам «спереди» и «сзади». Последний обработанный продукт и есть ответ; более низкие места — это те, что лежат после него в итоговом рейтинге (начало + перевёрнутый конец).
Ответ для файла: продукт 270, ниже него 484.
Ответ: 270 484
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v1.txt')
n = int(f.readline())
items = []
for i in range(1, n + 1):
a, b = map(int, f.readline().split())
items.append((min(a, b), i, a < b)) # (меньшее число, номер, меньшее — срок хранения?)
items.sort()
front, back = [], []
for m, i, is_storage in items:
if is_storage:
front.append(i)
else:
back.append(i)
rating = front + back[::-1]
last = items[-1][1]
print(last, len(rating) - 1 - rating.index(last))
Вариант 2
архив на диске
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве.
Шаг 1. Сколько файлов. Чтобы файлов было больше всего, берём самые маленькие: сортируем по возрастанию и набираем, пока помещаются. Помещается 321 файл (их сумма 6676 ≤ 6689).
Шаг 2. Самый большой файл. Оставляем 320 самых маленьких (сумма 6635) и на последнее место ставим самый большой файл, который ещё влезает: 6689 − 6635 = 54 — свободно; самый большой файл не больше этого — 54.
Ответ: 321 54
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v2.txt')
S, n = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))
total = k = 0
while k < n and total + a[k] <= S:
total += a[k]
k += 1
rest = S - (total - a[k - 1]) # место для последнего файла
print(k, max(x for x in a[k - 1:] if x <= rest))
Вариант 3
места в кинозале
В кинотеатре 10000 рядов по 60 мест в каждом. В файле записана информация о купленных билетах на сеанс. Найдите ряд с наибольшим номером, в котором есть два соседних свободных места, таких что слева и справа от них места заняты. Гарантируется, что такой ряд есть. В ответе запишите два числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные. В первой строке входного файла находится число N — количество занятых мест. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер места. Данные не упорядочены.
Идея. Сортируем занятые места по ряду и номеру места. В одном ряду два соседних занятых места a и b дают ровно два свободных места между собой, если b − a = 3. Просматриваем ряды от больших номеров к меньшим и в первом подходящем ряду берём первую такую пару.
Ответ для файла: ряд 9970, места 20 и 21 (заняты 19 и 22).
Ответ: 9970 20
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v3.txt')
n = int(f.readline())
seats = sorted(tuple(map(int, f.readline().split())) for _ in range(n))
best = None
for (r1, s1), (r2, s2) in zip(seats, seats[1:]):
if r1 == r2 and s2 - s1 == 3:
if best is None or r1 > best[0]:
best = (r1, s1 + 1) # места идут по возрастанию — первая пара в ряду наименьшая
print(*best)
Вариант 4
рейтинг продуктов
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Идея. Для каждого продукта важно только меньшее из двух чисел: продукт размещается, когда до него дойдёт очередь по возрастанию, то есть по своему минимальному числу. Если меньшее — срок хранения, продукт встаёт в начало (на первое свободное место), иначе — в конец.
Алгоритм. Сортируем продукты по минимальному числу, раскладываем по двум спискам «спереди» и «сзади». Последний обработанный продукт и есть ответ; более низкие места — это те, что лежат после него в итоговом рейтинге (начало + перевёрнутый конец).
Ответ для файла: продукт 756, ниже него 430.
Ответ: 756 430
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v4.txt')
n = int(f.readline())
items = []
for i in range(1, n + 1):
a, b = map(int, f.readline().split())
items.append((min(a, b), i, a < b)) # (меньшее число, номер, меньшее — срок хранения?)
items.sort()
front, back = [], []
for m, i, is_storage in items:
if is_storage:
front.append(i)
else:
back.append(i)
rating = front + back[::-1]
last = items[-1][1]
print(last, len(rating) - 1 - rating.index(last))
Вариант 5
архив на диске
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве.
Шаг 1. Сколько файлов. Чтобы файлов было больше всего, берём самые маленькие: сортируем по возрастанию и набираем, пока помещаются. Помещается 404 файла (их сумма 8861 ≤ 8884).
Шаг 2. Самый большой файл. Оставляем 403 самых маленьких (сумма 8816) и на последнее место ставим самый большой файл, который ещё влезает: 8884 − 8816 = 68 — свободно; самый большой файл не больше этого — 68.
Ответ: 404 68
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v5.txt')
S, n = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))
total = k = 0
while k < n and total + a[k] <= S:
total += a[k]
k += 1
rest = S - (total - a[k - 1]) # место для последнего файла
print(k, max(x for x in a[k - 1:] if x <= rest))
Вариант 6
рейтинг продуктов
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Идея. Для каждого продукта важно только меньшее из двух чисел: продукт размещается, когда до него дойдёт очередь по возрастанию, то есть по своему минимальному числу. Если меньшее — срок хранения, продукт встаёт в начало (на первое свободное место), иначе — в конец.
Алгоритм. Сортируем продукты по минимальному числу, раскладываем по двум спискам «спереди» и «сзади». Последний обработанный продукт и есть ответ; более низкие места — это те, что лежат после него в итоговом рейтинге (начало + перевёрнутый конец).
Ответ для файла: продукт 607, ниже него 451.
Ответ: 607 451
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v6.txt')
n = int(f.readline())
items = []
for i in range(1, n + 1):
a, b = map(int, f.readline().split())
items.append((min(a, b), i, a < b)) # (меньшее число, номер, меньшее — срок хранения?)
items.sort()
front, back = [], []
for m, i, is_storage in items:
if is_storage:
front.append(i)
else:
back.append(i)
rating = front + back[::-1]
last = items[-1][1]
print(last, len(rating) - 1 - rating.index(last))
Вариант 7
места в кинозале
В кинотеатре 20000 рядов по 80 мест в каждом. В файле записана информация о купленных билетах на сеанс. Найдите ряд с наибольшим номером, в котором есть два соседних свободных места, таких что слева и справа от них места заняты. Гарантируется, что такой ряд есть. В ответе запишите два числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные. В первой строке входного файла находится число N — количество занятых мест. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер места. Данные не упорядочены.
Идея. Сортируем занятые места по ряду и номеру места. В одном ряду два соседних занятых места a и b дают ровно два свободных места между собой, если b − a = 3. Просматриваем ряды от больших номеров к меньшим и в первом подходящем ряду берём первую такую пару.
Ответ для файла: ряд 16746, места 69 и 70 (заняты 68 и 71).
Ответ: 16746 69
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v7.txt')
n = int(f.readline())
seats = sorted(tuple(map(int, f.readline().split())) for _ in range(n))
best = None
for (r1, s1), (r2, s2) in zip(seats, seats[1:]):
if r1 == r2 and s2 - s1 == 3:
if best is None or r1 > best[0]:
best = (r1, s1 + 1) # места идут по возрастанию — первая пара в ряду наименьшая
print(*best)
Вариант 8
архив на диске
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве.
Шаг 1. Сколько файлов. Чтобы файлов было больше всего, берём самые маленькие: сортируем по возрастанию и набираем, пока помещаются. Помещается 225 файлов (их сумма 2581 ≤ 2600).
Шаг 2. Самый большой файл. Оставляем 224 самых маленьких (сумма 2557) и на последнее место ставим самый большой файл, который ещё влезает: 2600 − 2557 = 43 — свободно; самый большой файл не больше этого — 43.
Ответ: 225 43
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v8.txt')
S, n = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))
total = k = 0
while k < n and total + a[k] <= S:
total += a[k]
k += 1
rest = S - (total - a[k - 1]) # место для последнего файла
print(k, max(x for x in a[k - 1:] if x <= rest))
Вариант 9
рейтинг продуктов
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Идея. Для каждого продукта важно только меньшее из двух чисел: продукт размещается, когда до него дойдёт очередь по возрастанию, то есть по своему минимальному числу. Если меньшее — срок хранения, продукт встаёт в начало (на первое свободное место), иначе — в конец.
Алгоритм. Сортируем продукты по минимальному числу, раскладываем по двум спискам «спереди» и «сзади». Последний обработанный продукт и есть ответ; более низкие места — это те, что лежат после него в итоговом рейтинге (начало + перевёрнутый конец).
Ответ для файла: продукт 627, ниже него 446.
Ответ: 627 446
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v9.txt')
n = int(f.readline())
items = []
for i in range(1, n + 1):
a, b = map(int, f.readline().split())
items.append((min(a, b), i, a < b)) # (меньшее число, номер, меньшее — срок хранения?)
items.sort()
front, back = [], []
for m, i, is_storage in items:
if is_storage:
front.append(i)
else:
back.append(i)
rating = front + back[::-1]
last = items[-1][1]
print(last, len(rating) - 1 - rating.index(last))
Вариант 10
места в кинозале
В кинотеатре 10000 рядов по 60 мест в каждом. В файле записана информация о купленных билетах на сеанс. Найдите ряд с наибольшим номером, в котором есть два соседних свободных места, таких что слева и справа от них места заняты. Гарантируется, что такой ряд есть. В ответе запишите два числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные. В первой строке входного файла находится число N — количество занятых мест. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер места. Данные не упорядочены.
Идея. Сортируем занятые места по ряду и номеру места. В одном ряду два соседних занятых места a и b дают ровно два свободных места между собой, если b − a = 3. Просматриваем ряды от больших номеров к меньшим и в первом подходящем ряду берём первую такую пару.
Ответ для файла: ряд 7433, места 9 и 10 (заняты 8 и 11).
Ответ: 7433 9
Решение на Python. Положите файл варианта рядом с программой.
f = open('Ege26_v10.txt')
n = int(f.readline())
seats = sorted(tuple(map(int, f.readline().split())) for _ in range(n))
best = None
for (r1, s1), (r2, s2) in zip(seats, seats[1:]):
if r1 == r2 and s2 - s1 == 3:
if best is None or r1 > best[0]:
best = (r1, s1 + 1) # места идут по возрастанию — первая пара в ряду наименьшая
print(*best)
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
рейтинг продуктов
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве.
В кинотеатре 20000 рядов по 80 мест в каждом. В файле записана информация о купленных билетах на сеанс. Найдите ряд с наибольшим номером, в котором есть два соседних свободных места, таких что слева и справа от них места заняты. Гарантируется, что такой ряд есть. В ответе запишите два числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные. В первой строке входного файла находится число N — количество занятых мест. Каждая из следующих N строк содержит два натуральных числа: номер ряда и номер места. Данные не упорядочены.
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы. В рейтинговом списке маркетологи располагают продукты по следующему алгоритму: – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию; – если минимальное число в этом упорядоченном списке — срок хранения, то продукт в рейтинге занимает первое свободное место от его начала; – если минимальное число — срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга; – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов. Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные. В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество продуктов. Следующие N строк содержат пары чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Пример. Для 5 продуктов (30 50), (100 155), (150 170), (10 160), (120 55) порядок в рейтинге: 4, 1, 2, 3, 5. Последним займёт место продукт 3, ниже него один продукт. Ответ: 3 1.
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве.