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

ЕГЭ, Информатика: 26. Прикладная задача: все задания

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

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которые можно провести в конференц-зале, и самое позднее время окончания последнего мероприятия.

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

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

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

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

5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, по заявкам $2$, $3$ и $5$. Конференц-зал освободится самое позднее на $180$-й минуте, если состоятся мероприятия по заявкам $2$, $4$ и $5$.

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

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

Поэтому считаем динамику: для каждого мероприятия $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$.

Показать
Очки опыта 20
Спросить Зави
22. Задание #298080
Решено верно
Решено неверно
Сообщить о проблеме

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение $1$ мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение $24$ ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

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

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

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

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

2
5
30 60
40 1000
59 60
61 1000
1010 1440

При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку $1$, так как ячейки $1$ и $2$ будут свободны.

Это прямое моделирование. Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени сдачи багажа — обслуживать пассажиров надо в порядке прихода.

Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $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$.

Показать
Очки опыта 20
Спросить Зави
23. Задание #298078
Решено верно
Решено неверно
Сообщить о проблеме

Каждый кандидат в отряд космонавтов проходит $3$ испытания, за каждое из которых можно получить от $0$ до $100$ баллов. Кроме того, можно получить дополнительно от $0$ до $10$ баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) – натуральное число, не превышающее $100000$. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с бо́льшими баллами за собеседование, а при равенстве и этих баллов – с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.

Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, в противном случае полупроходной балл отсутствует.

В ответе запишите два целых числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл. Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.

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

В первой строке входного файла находятся два натуральных числа, не превышающих $10000$, через пробел: число $N$ – количество кандидатов и число $K$ – количество мест в отряде. В следующих $N$ строках находятся по $5$ чисел через пробел: ID кандидата (натуральное число, не превышающее $100000$) и четыре целых неотрицательных числа – сначала результаты испытаний, затем результат собеседования.

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

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

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

6 4
4 80 80 80 0
7 50 80 100 10
11 80 80 70 10
10 100 100 100 2
6 90 90 90 9
2 70 80 80 8

При таких исходных данных рейтинговый список из ID составлен следующим образом: $10$ $6$ $7$ $11$ $4$ $2$. Два кандидата с баллами $302$ и $279$ зачислены, проходной балл $279$. На оставшиеся два места претендуют три человека, набравшие по $240$ баллов, хотя из троих будут зачислены только двое. Таким образом, $240$ – полупроходной балл. Ответ: $6$ $3$.

Сначала строим рейтинг. Сортировка тройная: сумма всех четырёх баллов по убыванию, затем баллы за собеседование по убыванию, затем 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$.

Показать
Очки опыта 20
Спросить Зави
24. Задание #298083
Решено верно
Решено неверно
Сообщить о проблеме

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.

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

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

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

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

5
10 150
100 120
131 170
150 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам $2$, $3$ и $5$. Максимальный перерыв между двумя последними мероприятиями составит $20$ мин., если состоятся мероприятия по заявкам $2$, $4$ и $5$.

Два мероприятия совместимы, если конец одного не позже начала другого. Максимальное количество даёт классическая жадность: сортируем по времени окончания и берём каждое, которое начинается не раньше конца предыдущего взятого.

Второй вопрос жадность не решает: расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому считаем динамику: для каждого мероприятия $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$.

Показать
Очки опыта 20
Спросить Зави
25. Задание #298085
Решено верно
Решено неверно
Сообщить о проблеме

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела (в Кбайт), выполненной не позднее $11{:}59{:}59$.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1000000$) – количество строк в журнале и $K$ ($K < 1000000$) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1000000$) – идентификатор клиентского устройства и $S$ ($S < K$) – объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала наибольший суммарный объём данных, переданных на сервер с двух устройств, а затем объём последней по времени резервной копии (в Кбайт), выполненной не позднее $11{:}59{:}59$.

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

8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в $05{:}05{:}05$ (в объёме $130000$ Кбайт), в $07{:}07{:}07$ (в объёме $90000$ Кбайт), в $21{:}21{:}21$ (в объёме $122000$ Кбайт) и в $23{:}23{:}23$ (в объёме $120000$ Кбайт). Всего на сервер передано $596000$ Кбайт данных: $158000$, $122000$, $182000$ и $134000$ Кбайт от клиентов с идентификаторами $101$, $202$, $303$ и $404$ соответственно. Ответ для приведённого примера: $340000$ $90000$.

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

Моделирование раздела памяти прежнее. Держим счётчик накопленного объёма; если накопленное плюс новый запрос превышает вместимость $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$.

Показать
Очки опыта 20
Спросить Зави
26. Задание #298089
Решено верно
Решено неверно
Сообщить о проблеме

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор клиентского устройства, с которого на сервер был передан наибольший суммарный объём данных, не превышающий $150000$ Кбайт, а также сумму объёмов двух наибольших резервных копий специального раздела (в Кбайт), выполненных не ранее $12{:}00{:}00$.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1000000$) – количество строк в журнале и $K$ ($K < 1000000$) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1000000$) – идентификатор клиентского устройства и $S$ ($S < K$) – объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала идентификатор устройства, с которого на сервер был передан наибольший суммарный объём данных, не превышающий $150000$ Кбайт, а затем сумму объёмов двух наибольших резервных копий специального раздела (в Кбайт), выполненных не ранее $12{:}00{:}00$.

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

8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в $05{:}05{:}05$ (в объёме $130000$ Кбайт), в $07{:}07{:}07$ (в объёме $90000$ Кбайт), в $21{:}21{:}21$ (в объёме $122000$ Кбайт) и в $23{:}23{:}23$ (в объёме $120000$ Кбайт). Всего на сервер передано $596000$ Кбайт данных: $158000$, $122000$, $182000$ и $134000$ Кбайт от клиентов с идентификаторами $101$, $202$, $303$ и $404$ соответственно. Ответ для приведённого примера: $404$ $242000$.

Обе величины считаются за один проход, но у каждой свой фильтр — и оба надо применить аккуратно.

По клиентам суммы копятся за все сутки, без ограничения по времени. Зато при выборе победителя действует потолок: нужен наибольший объём среди тех, что не превышают $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$.

Показать
Очки опыта 20
Спросить Зави
27. Задание #298090
Решено верно
Решено неверно
Сообщить о проблеме

Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.

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

В первой строке входного файла находится число $N$ – количество занятых мест (натуральное число, не превышающее $10000$). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100000$: номер ряда и номер занятого места.

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

Два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.
Пример входного файла:

7
40 3
40 6
60 33
50 125
50 128
50 64
50 67

Условию задачи удовлетворяют три пары чисел: $40$ и $4$, $50$ и $126$, $50$ и $65$. Ответ для приведённого примера: $50$ $65$.

Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $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$, но подходящей пары в нём нет, поэтому брать его нельзя.

Показать
Очки опыта 20
Спросить Зави
28. Задание #298093
Решено верно
Решено неверно
Сообщить о проблеме

В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $6$ единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет $3$ единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон $30$, $40$ и $43$ или $32$, $40$ и $43$ соответственно, т.е. количество коробок равно $3$, а длина стороны самой маленькой коробки равна $32$.

Отсортируем длины сторон по возрастанию. Матрёшка — это цепочка, в которой каждая следующая коробка больше предыдущей хотя бы на $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$.

Показать
Очки опыта 20
Спросить Зави
29. Задание #298096
Решено верно
Решено неверно
Сообщить о проблеме

Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар свободных мест.

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

В первой строке входного файла находится число $N$ – количество занятых мест (натуральное число, не превышающее $10000$). Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $100000$: номер ряда и номер занятого места.

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

Два целых неотрицательных числа: номер ряда и наименьший номер места в выбранной паре.

Пример входного файла:

7
40 3
40 6
60 33
50 125
50 128
50 64
50 67

Условию задачи удовлетворяют три пары чисел: $40$ и $4$, $50$ и $126$, $50$ и $65$. Ответ для приведённого примера: $50$ $65$.

Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $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$, но подходящей пары в нём нет, поэтому брать его нельзя.

Показать
Очки опыта 20
Спросить Зави
30. Задание #298100
Решено верно
Решено неверно
Сообщить о проблеме

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее $11{:}59{:}59$.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1000000$) – количество строк в журнале и $K$ ($K < 1000000$) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1000000$) – идентификатор клиентского устройства и $S$ ($S < K$) – объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных, а затем сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, выполненных не позднее $11{:}59{:}59$.

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

8 140000
01:01:01 101 20000
03:03:03 202 110000
05:05:05 101 90000
07:07:07 303 62000
10:10:10 101 48000
15:15:15 202 12000
21:21:21 303 120000
23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в $05{:}05{:}05$ (в объёме $130000$ Кбайт), в $07{:}07{:}07$ (в объёме $90000$ Кбайт), в $21{:}21{:}21$ (в объёме $122000$ Кбайт) и в $23{:}23{:}23$ (в объёме $120000$ Кбайт). Всего на сервер передано $596000$ Кбайт данных: $158000$, $122000$, $182000$ и $134000$ Кбайт от клиентов с идентификаторами $101$, $202$, $303$ и $404$ соответственно. Ответ для приведённого примера: $303$ $220000$.

Обе величины считаются за один проход, но ограничение по времени здесь наложено только на резервные копии — суммы по клиентам берутся за все сутки без всяких фильтров.

Моделирование раздела памяти стандартное: держим счётчик накопленного объёма, и если накопленное плюс новый запрос превышает вместимость $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$.

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

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