ЕГЭ, Информатика: 26. Прикладная задача: все задания
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которые можно провести в конференц-зале, и самое позднее время окончания последнего мероприятия.
Два мероприятия совместимы, если конец одного не позже начала другого. Максимальное количество находится классической жадностью: сортируем по времени окончания и берём каждое, которое начинается не раньше конца предыдущего взятого.
Но второй вопрос жадность не решает. Расписаний с максимальным количеством мероприятий много, и то, которое строит жадность, заканчивается раньше остальных — она специально выбирает самые ранние концы. Здесь же нужно самое позднее окончание среди всех оптимальных расписаний.
Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$. Затем среди всех мероприятий с $cnt[i] = K$ берём наибольшее время окончания: каждое такое мероприятие может оказаться последним в некотором оптимальном расписании.
f = open('26-21.txt')
n = int(f.readline())
ev = [tuple(map(int, f.readline().split())) for _ in range(n)]
ev.sort(key=lambda x: x[1]) # по времени окончания
cnt = [0] * n # макс. число мероприятий в цепочке, кончающейся i-м
for i, (a, b) in enumerate(ev):
best = 0
for k in range(i):
if ev[k][1] <= a and cnt[k] > best: # конец не позже начала
best = cnt[k]
cnt[i] = best + 1
K = max(cnt)
last = max(b for (a, b), c in zip(ev, cnt) if c == K)
print(K, last) # 19 1362
Проверка. Заявок $912$, жадный подсчёт тоже даёт $19$ мероприятий, но его расписание освобождает зал уже на $1088$-й минуте — почти на пять часов раньше найденного оптимума. При этом $1362$ меньше, чем самое позднее окончание в файле вообще ($1400$): то мероприятие в цепочку из $19$ штук не встраивается. На типовом примере из условия программа выдаёт $3$ и $180$.
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение $1$ мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение $24$ ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
Это прямое моделирование. Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени сдачи багажа — обслуживать пассажиров надо в порядке прихода.
Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $t$ может занять ячейку, если это число меньше $t$ — так реализуется правило «начиная со следующей минуты после освобождения». Перебираем ячейки по возрастанию номера и берём первую подходящую, чем и обеспечивается требование про минимальный номер. Если подходящей нет, пассажир уходит.
Попутно считаем принятых и запоминаем, кто занял ячейку последним по времени; при совпадении времени берём меньший номер ячейки.
f = open('26-22.txt')
K = int(f.readline())
N = int(f.readline())
req = [tuple(map(int, f.readline().split())) for _ in range(N)]
req.sort() # по времени сдачи багажа
free = [0] * K # время, когда ячейка освободится
cnt = 0
last_t, last_cell = -1, None
for t, e in req:
for i in range(K):
if free[i] < t: # доступна со следующей минуты
free[i] = e
cnt += 1
if t > last_t:
last_t, last_cell = t, i + 1
elif t == last_t and i + 1 < last_cell:
last_cell = i + 1
break
print(cnt, last_cell) # 344 53
Проверка. Ячеек $210$, заявок $987$, успешными оказались $344$ пассажира. Последняя сдача среди них произошла на $999$-й минуте, и такой пассажир был один — он занял ячейку $53$. На типовом примере из условия программа выдаёт $4$ и $1$.
Каждый кандидат в отряд космонавтов проходит $3$ испытания, за каждое из которых можно получить от $0$ до $100$ баллов. Кроме того, можно получить дополнительно от $0$ до $10$ баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) – натуральное число, не превышающее $100000$. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с бо́льшими баллами за собеседование, а при равенстве и этих баллов – с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.
Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, в противном случае полупроходной балл отсутствует.
В ответе запишите два целых числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл. Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.
Сначала строим рейтинг. Сортировка тройная: сумма всех четырёх баллов по убыванию, затем баллы за собеседование по убыванию, затем ID по возрастанию. Чтобы обойтись одной обычной сортировкой, кладём в ключ сумму и собеседование со знаком минус, а ID как есть.
Дальше ключевой момент — определение проходного балла. Он не равен просто баллу кандидата, стоящего на $K$-й строчке рейтинга: по условию это минимальная сумма, с которой зачисляются все её набравшие. Поэтому идём по рейтингу группами кандидатов с одинаковой суммой и берём группу целиком, только если она полностью помещается в оставшиеся места. Как только очередная группа не влезает, останавливаемся. Последний зачисленный кандидат и есть ответ на первый вопрос.
Та самая группа, которая не поместилась, и даёт полупроходной балл — при условии, что места ещё остались. Если после зачисления всех с проходным баллом отряд заполнен ровно или кандидаты кончились, полупроходного балла нет и в ответ идёт ноль.
f = open('26-23.txt')
n, K = map(int, f.readline().split())
c = []
for _ in range(n):
v = list(map(int, f.readline().split()))
c.append((-(v[1] + v[2] + v[3] + v[4]), -v[4], v[0])) # сумма, собеседование, ID
c.sort()
admitted, i, last = 0, 0, None
while i < n:
j = i
while j < n and c[j][0] == c[i][0]: # группа с одинаковой суммой
j += 1
if admitted + (j - i) > K: # группа целиком не влезает
break
admitted, last, i = j, c[j-1][2], j
half = (j - i) if (i < n and admitted < K) else 0
print(last, half) # 45539 127
Проверка. Кандидатов $9996$, мест $1076$. Проходной балл равен $280$, его и все более высокие набрали $955$ человек, последний из них — ID $45539$. Остаётся $121$ место, а на него претендуют $127$ кандидатов с суммой $279$ — это и есть полупроходной балл. На типовом примере из условия программа выдаёт $6$ и $3$.
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Два мероприятия совместимы, если конец одного не позже начала другого. Максимальное количество даёт классическая жадность: сортируем по времени окончания и берём каждое, которое начинается не раньше конца предыдущего взятого.
Второй вопрос жадность не решает: расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$.
Теперь пара последних мероприятий. Последнее — это любое $j$ с $cnt[j] = K$, а предыдущее — любое совместимое с ним $i$, у которого $cnt[i] = K-1$: тогда цепочка из $K-1$ мероприятий заканчивается на $i$, а $j$ добавляется последним. Перерыв равен разности между началом $j$ и концом $i$, берём наибольший.
f = open('26-24.txt')
n = int(f.readline())
ev = [tuple(map(int, f.readline().split())) for _ in range(n)]
ev.sort(key=lambda x: x[1]) # по времени окончания
cnt = [0] * n # макс. число мероприятий в цепочке, кончающейся i-м
for i, (a, b) in enumerate(ev):
best = 0
for k in range(i):
if ev[k][1] <= a and cnt[k] > best: # конец не позже начала
best = cnt[k]
cnt[i] = best + 1
K = max(cnt)
gap = 0
for j, (a, b) in enumerate(ev):
if cnt[j] != K: # j должно быть последним в цепочке
continue
for i in range(j):
if cnt[i] == K - 1 and ev[i][1] <= a:
gap = max(gap, a - ev[i][1])
print(K, gap) # 26 11
Проверка. Заявок $990$, жадный подсчёт на том же файле тоже даёт $26$ мероприятий. Перерыв вышел небольшим — $11$ минут: заявки плотные, и на последнем шаге свободы почти не остаётся. На типовом примере из условия программа выдаёт $3$ и $20$.
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела (в Кбайт), выполненной не позднее $11{:}59{:}59$.
Обе величины считаются за один проход по журналу, но обратите внимание на разницу с похожей задачей: здесь ограничение по времени наложено только на резервные копии, а суммы по клиентам берутся за все сутки.
Моделирование раздела памяти прежнее. Держим счётчик накопленного объёма; если накопленное плюс новый запрос превышает вместимость $K$, сервер делает копию того, что уже лежит в разделе, обнуляет счётчик и только потом кладёт туда новый запрос. В копию попадает объём до добавления текущего запроса.
Нужна не самая большая копия, а последняя по времени среди сделанных не позднее $11{:}59{:}59$. Поскольку журнал идёт в хронологическом порядке, достаточно просто перезаписывать переменную при каждой подходящей копии — в конце в ней останется нужная. Время сравниваем прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически.
Суммы по клиентам копим в словаре без всяких условий, затем берём два наибольших значения и складываем.
from collections import defaultdict
f = open('26-25.txt')
n, K = map(int, f.readline().split())
total = defaultdict(int)
cur = 0
last_backup = 0
for _ in range(n):
t, c, s = f.readline().split()
s = int(s)
if cur + s > K: # свободной памяти не хватает
if t <= '11:59:59': # копия сделана не позднее 11:59:59
last_backup = cur
cur = 0
cur += s
total[int(c)] += s
top = sorted(total.values(), reverse=True)
print(top[0] + top[1], last_backup) # 481895 21328
Проверка. В журнале $15007$ записей, вместимость раздела $23000$ Кбайт, копий получилось $1115$. Последняя до полудня сделана в $11{:}59{:}10$ в объёме $21328$ Кбайт. Два самых активных клиента — $5382$ с объёмом $246899$ Кбайт и $4637$ с $234996$, в сумме $481895$. На типовом примере из условия программа выдаёт $340000$ и $90000$.
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор клиентского устройства, с которого на сервер был передан наибольший суммарный объём данных, не превышающий $150000$ Кбайт, а также сумму объёмов двух наибольших резервных копий специального раздела (в Кбайт), выполненных не ранее $12{:}00{:}00$.
Обе величины считаются за один проход, но у каждой свой фильтр — и оба надо применить аккуратно.
По клиентам суммы копятся за все сутки, без ограничения по времени. Зато при выборе победителя действует потолок: нужен наибольший объём среди тех, что не превышают $150000$ Кбайт. Это не «максимум минус что-то», а именно максимум по отфильтрованному множеству — клиентов с бо́льшим объёмом мы просто не рассматриваем. В примере из условия видно, как это работает: лидер по объёму — устройство $303$ со $182000$, но оно за потолком, и ответом становится $404$ со $134000$.
Моделирование раздела памяти прежнее: если накопленное плюс новый запрос превышает вместимость $K$, сервер копирует то, что уже лежит в разделе, обнуляет счётчик и кладёт туда новый запрос. В копилку кандидатов на две наибольшие копии попадают только те, что сделаны не ранее $12{:}00{:}00$. Время сравниваем прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически.
from collections import defaultdict
f = open('26-26.txt')
n, K = map(int, f.readline().split())
total = defaultdict(int)
backups = []
cur = 0
for _ in range(n):
t, c, s = f.readline().split()
s = int(s)
if cur + s > K: # свободной памяти не хватает
if t >= '12:00:00': # копия сделана не ранее 12:00:00
backups.append(cur)
cur = 0
cur += s
total[int(c)] += s
best = max((v for v in total.values() if v <= 150000))
client = min(c for c, v in total.items() if v == best)
backups.sort(reverse=True)
print(client, backups[0] + backups[1]) # 1006 46566
Проверка. В журнале $15003$ записи, вместимость раздела $23285$ Кбайт. Копий всего $1112$, из них после полудня — $564$; две наибольшие оказались по $23285$ и $23281$ Кбайт, в сумме $46566$. Максимум по всем клиентам вообще равен $239933$ Кбайт, но он выше потолка; наибольший подходящий объём — $148122$ Кбайт у устройства $1006$. На типовом примере из условия программа выдаёт $404$ и $242000$.
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.
Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $a$ и $b$ в одном ряду, между которыми ровно два свободных. Это в точности условие $b - a = 3$.
Значит группируем занятые места по рядам, каждый ряд сортируем и смотрим только на соседние элементы отсортированного списка: если разница равна $3$, найдена подходящая пара, её меньший номер равен $a+1$. Перебирать все места ряда не нужно — их номера доходят до $100000$, а занятых всего $10000$.
Дальше по условию: сначала выбираем ряд с наибольшим номером среди тех, где такая пара нашлась, и уже внутри него берём наименьший номер места.
from collections import defaultdict
f = open('26-27.txt')
n = int(f.readline())
rows = defaultdict(list)
for _ in range(n):
r, p = map(int, f.readline().split())
rows[r].append(p)
best_row, best_seat = -1, None
for r, seats in rows.items():
seats = sorted(set(seats))
# разница 3 между занятыми = ровно два свободных места между ними
pairs = [seats[i] + 1 for i in range(len(seats) - 1) if seats[i+1] - seats[i] == 3]
if pairs and r > best_row:
best_row, best_seat = r, min(pairs)
print(best_row, best_seat) # 80000 80174
Проверка. Подходящих рядов в файле $997$, максимальный по номеру из них — $80000$. В нём нашлись три подходящие пары, начинающиеся с мест $80174$, $91708$ и $93218$; наименьшая идёт в ответ. Обратите внимание, что наибольший номер ряда в файле вообще — $99919$, но подходящей пары в нём нет, поэтому брать его нельзя.
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $6$ единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Отсортируем длины сторон по возрастанию. Матрёшка — это цепочка, в которой каждая следующая коробка больше предыдущей хотя бы на $6$. Максимальную длину даёт обычная жадность: идём по возрастанию и берём коробку, если она подходит к последней взятой.
Со вторым вопросом жадность не справляется: она стартует с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому для каждой коробки считаем $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.
Работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 6$. Её и находим двоичным поиском, а массив заполняем справа налево.
Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.
from bisect import bisect_left
f = open('26-28.txt')
n = int(f.readline())
a = sorted(int(f.readline()) for _ in range(n))
ln = [1] * n # длина макс. цепочки, начинающейся с i-й коробки
for i in range(n-1, -1, -1):
j = bisect_left(a, a[i] + 6) # первая коробка, в которую влезет i-я
if j < n:
ln[i] = 1 + ln[j]
K = max(ln)
smallest = max(a[i] for i in range(n) if ln[i] == K)
print(K, smallest) # 1511 54
Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $1511$ коробок. Стартовать можно с любой коробки от $50$ до $54$ — все дают ровно $1511$ звеньев, а со следующей уже только $1510$. Поэтому в ответ идёт наибольшая из подходящих, то есть $54$. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.
Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $a$ и $b$ в одном ряду, между которыми ровно два свободных. Это в точности условие $b - a = 3$.
Значит группируем занятые места по рядам, каждый ряд сортируем и смотрим только на соседние элементы отсортированного списка: если разница равна $3$, найдена подходящая пара, её меньший номер равен $a+1$. Перебирать все места ряда не нужно — их номера доходят до $100000$, а занятых всего $10000$.
Дальше по условию: сначала выбираем ряд с наибольшим номером среди тех, где такая пара нашлась, и уже внутри него берём наименьший номер места.
from collections import defaultdict
f = open('26-29.txt')
n = int(f.readline())
rows = defaultdict(list)
for _ in range(n):
r, p = map(int, f.readline().split())
rows[r].append(p)
best_row, best_seat = -1, None
for r, seats in rows.items():
seats = sorted(set(seats))
# разница 3 между занятыми = ровно два свободных места между ними
pairs = [seats[i] + 1 for i in range(len(seats) - 1) if seats[i+1] - seats[i] == 3]
if pairs and r > best_row:
best_row, best_seat = r, min(pairs)
print(best_row, best_seat) # 79936 78782
Проверка. Занятых мест $9986$, подходящих рядов $996$, максимальный по номеру из них — $79936$. В нём нашлись три подходящие пары, начинающиеся с мест $78782$, $85874$ и $86480$; наименьшая идёт в ответ. Наибольший номер ряда в файле вообще — $99998$, но подходящей пары в нём нет, поэтому брать его нельзя.
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее $11{:}59{:}59$.
Обе величины считаются за один проход, но ограничение по времени здесь наложено только на резервные копии — суммы по клиентам берутся за все сутки без всяких фильтров.
Моделирование раздела памяти стандартное: держим счётчик накопленного объёма, и если накопленное плюс новый запрос превышает вместимость $K$, сервер копирует то, что уже лежит в разделе, обнуляет счётчик и только потом кладёт туда новый запрос. Порядок важен: в копию попадает объём до добавления текущего запроса. В список кандидатов на две наибольшие копии берём только те, что созданы не позднее $11{:}59{:}59$. Время сравниваем прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически.
Суммы по клиентам копим в словаре и в конце берём клиента с наибольшим значением.
from collections import defaultdict
f = open('26-30.txt')
n, K = map(int, f.readline().split())
total = defaultdict(int)
backups = []
cur = 0
for _ in range(n):
t, c, s = f.readline().split()
s = int(s)
if cur + s > K: # свободной памяти не хватает
if t <= '11:59:59': # копия создана не позднее 11:59:59
backups.append(cur)
cur = 0
cur += s
total[int(c)] += s
best = max(total, key=lambda c: total[c])
backups.sort(reverse=True)
print(best, backups[0] + backups[1]) # 7040 52204
Проверка. В журнале $15001$ запись, вместимость раздела $26107$ Кбайт. Копий всего $1072$, из них до полудня — $534$; две наибольшие оказались по $26102$ Кбайт каждая, в сумме $52204$. По клиентам лидирует устройство $7040$ с объёмом $303454$ Кбайт, следующее — $4783$ с $294379$. На типовом примере из условия программа выдаёт $303$ и $220000$.