26. Прикладная задача: все задания

Место свободно, если его нет в списке занятых. Нужна пара соседних свободных мест, окружённая занятыми — то есть занятые места $a$ и $b$ в одном ряду, между которыми ровно два свободных. Это в точности условие $b — a = 3$.

Значит группируем занятые места по рядам, каждый ряд сортируем и смотрим только на соседние элементы отсортированного списка: если разница равна $3$, найдена подходящая пара, её меньший номер равен $a+1$. Перебирать все места ряда не нужно — их номера доходят до $100000$, а занятых всего $10000$.

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

from collections import defaultdict

f = open('26-01.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)   # 69969 58998

Проверка. Подходящих рядов в файле $994$ штуки, максимальный по номеру из них — $69969$. В нём занято $11$ мест и нашлось три подходящих пары, начинающихся с мест $58998$, $80983$ и $93106$; наименьшая из них и идёт в ответ.

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

Вторая часть сложнее, потому что расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому вместо жадности считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ и есть ответ на первый вопрос, обозначим его $K$.

Теперь пара последних мероприятий. Последнее — это любое $j$ с $cnt[j] = K$, а предыдущее — любое совместимое с ним $i$, у которого $cnt[i] = K-1$: тогда цепочка из $K-1$ мероприятий заканчивается на $i$, а $j$ добавляется двадцать пятым. Перерыв равен разности между началом $j$ и концом $i$, берём наибольший.

f = open('26-02.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)   # 25 16

Проверка. Простой подсчёт на том же файле тоже даёт $25$ мероприятий. На типовом примере из условия программа выдаёт $3$ и $20$, что совпадает с приведённым разбором.

Квадратичная динамика здесь вполне уместна: при $N \le 1000$ это порядка миллиона операций.

Ключ в том, что «перед местом» означает то же самое место в предыдущих рядах. Значит зал распадается на $K$ независимых вертикальных линий: для каждого номера места мы смотрим только на свои ряды. Перебирать все клетки нельзя — их до десяти миллиардов, а занятых всего $10000$.

Внутри одной линии интересны лишь занятые ряды. Отсортируем их. Между двумя соседними занятыми рядами лежит участок свободных, и выгоднее всего сесть в самом дальнем ряду этого участка: тогда перед нами окажется весь участок целиком. Если предыдущий занятый ряд имеет номер $prev$, а выбранное место стоит в ряду $r$, то свободных перед ним ровно $r — prev — 1$.

Так что для каждой линии достаточно пройтись по занятым рядам, для каждого взять ряд непосредственно перед ним, а в конце отдельно рассмотреть хвост до последнего ряда зала. Плюс отдельная ветка на случай, когда какой-то номер места не занят вообще нигде: тогда можно сесть в самый дальний ряд $M$, и перед нами будут свободны все $M-1$ рядов.

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

from collections import defaultdict

f = open('26-03.txt')
N, M, K = map(int, f.readline().split())

occ = defaultdict(list)                  # номер места -> список занятых рядов
for _ in range(N):
    r, p = map(int, f.readline().split())
    occ[p].append(r)

best, best_row = -1, None
def upd(cnt, row):
    global best, best_row
    if cnt > best or (cnt == best and row < best_row):
        best, best_row = cnt, row

if len(occ) < K:                         # есть место, свободное во всех рядах
    upd(M - 1, M)

for p, rows in occ.items():
    rows.sort()
    prev = 0
    for o in rows:
        r = o - 1                        # самый дальний свободный ряд перед занятым
        if r > prev:
            upd(r - prev - 1, r)
        prev = o
    if M > prev:                         # хвост до конца зала
        upd(M - prev - 1, M)

print(best_row, best)   # 68217 33508

Проверка. В файле $N = 9996$, $M = 99931$, $K = 3332$, причём занятые места покрывают все $3332$ номера, так что ветка с полностью свободной линией не сработала. Ответ даёт место номер $620$ в ряду $68217$: само оно свободно, и перед ним подряд свободны ровно $33508$ кресел с тем же номером. На типовом примере из условия программа выдаёт $4$ и $3$.

Первая часть стандартная: чтобы влезло как можно больше контейнеров, надо брать самые лёгкие. Сортируем массы по возрастанию и набираем их подряд, пока суммарная масса не превысит грузоподъёмность. Полученное количество $k$ и есть максимум.

Вторая часть требует аккуратности. Спрашивается не про самый тяжёлый контейнер конкретного набора, а про максимально возможный среди всех наборов размера $k$. Чтобы освободить как можно больше места под один тяжёлый контейнер, остальные $k-1$ надо взять самыми лёгкими. Считаем их суммарную массу, вычитаем из грузоподъёмности и ищем среди оставшихся контейнеров самый тяжёлый, который в этот остаток укладывается.

f = open('26-04.txt')
S, N = map(int, f.readline().split())
w = sorted(int(f.readline()) for _ in range(N))

total, k = 0, 0
for x in w:                              # набираем самые лёгкие
    if total + x > S:
        break
    total += x
    k += 1

base = sum(w[:k-1])                      # k-1 самых лёгких берём обязательно
heaviest = max(x for x in w[k-1:] if base + x <= S)

print(k, heaviest)   # 1612 90

Проверка. Грузоподъёмность $99990$, контейнеров $9999$ общей массой $749769$, массы лежат в диапазоне от $60$ до $90$. Максимум помещается $1612$ контейнеров. Масса $1611$ самых лёгких равна $99867$, свободного места остаётся $123$, и самый тяжёлый контейнер в файле массой $90$ туда свободно входит: $99867 + 90 = 99957 \le 99990$. На типовом примере из условия программа выдаёт $2$ и $50$.

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

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

Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$. Затем среди всех мероприятий с $cnt[i] = K$ берём наибольшее время окончания: каждое такое мероприятие может быть последним в некотором оптимальном расписании.

f = open('26-05.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)   # 53 1300

Проверка. Жадный подсчёт на том же файле тоже даёт $53$ мероприятия, но его расписание освобождает зал уже на $1057$-й минуте — на четверть суток раньше найденного оптимума. При этом $1300$ меньше, чем самое позднее окончание в файле вообще ($1399$): то мероприятие в цепочку из $53$ штук не встраивается. На типовом примере из условия программа выдаёт $3$ и $180$.

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

Со вторым вопросом жадность не справляется: она начинает с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому считаем для каждой коробки $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.

Тут есть удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 3$. Её и находим двоичным поиском, а массив заполняем справа налево.

Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.

from bisect import bisect_left

f = open('26-06.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] + 3)   # первая коробка, в которую влезет 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)   # 2767 51

Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $2767$ коробок. Цепочка, стартующая с коробки $51$, действительно содержит $2767$ штук, а если бы мы начали со следующей по размеру коробки $52$, вышло бы уже только $2766$. На типовом примере из условия программа выдаёт $3$ и $32$.

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

Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $t$ может занять ячейку, если она освободилась строго раньше, то есть если записанное для неё время меньше $t$. Это ровно та формулировка «начиная со следующей минуты» из условия: ячейка, освобождённая в минуту $60$, доступна с минуты $61$.

Перебираем ячейки по возрастанию номера и берём первую подходящую — так выполняется требование про минимальный номер. Если подходящей нет, пассажир уходит. Попутно считаем успешных пассажиров и запоминаем, кто занял ячейку последним по времени; при совпадении времени берём меньший номер ячейки.

f = open('26-07.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)   # 368 83

Проверка. Ячеек $210$, заявок $987$, успешными оказались $368$ пассажиров. Последняя сдача багажа среди них произошла на $997$-й минуте, и в этот момент был всего один такой пассажир — он занял ячейку $83$. На типовом примере из условия программа выдаёт $4$ и $1$.

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

Со вторым вопросом жадность не справляется: она начинает с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому считаем для каждой коробки $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.

Тут работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 10$. Её и находим двоичным поиском, а массив заполняем справа налево.

Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.

from bisect import bisect_left

f = open('26-08.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] + 10)   # первая коробка, в которую влезет 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)   # 935 51

Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $935$ коробок. Файл тот же, что в задаче с разницей $3$, где ответ был $2767$ и $51$: при более жёстком шаге цепочка ожидаемо укоротилась почти втрое, а стартовая коробка осталась прежней. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.

Это прямое моделирование описанного алгоритма. Собираем все $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$.

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

Со вторым вопросом жадность не справляется: она стартует с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому для каждой коробки считаем $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.

Работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 7$. Её и находим двоичным поиском, а массив заполняем справа налево.

Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.

from bisect import bisect_left

f = open('26-10.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] + 7)   # первая коробка, в которую влезет 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)   # 1306 52

Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $1306$ коробок. Стартовать можно с коробок $50$, $51$ или $52$ — все три дают ровно $1306$ звеньев, а вот с $53$ получается уже только $1305$. Поэтому ответом идёт наибольшая из подходящих, то есть $52$. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.

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

Для каждой ячейки храним одно число: момент, когда она освобождается. Пассажир с временем прихода $t$ может занять ячейку, если она освободилась строго раньше, то есть если записанное для неё время меньше $t$. Это и есть формулировка «начиная со следующей минуты»: ячейка, освобождённая в минуту $60$, доступна с минуты $61$.

Перебираем ячейки по возрастанию номера и берём первую подходящую — так выполняется требование про минимальный номер. Если подходящей нет, пассажир уходит. Попутно считаем успешных пассажиров и запоминаем, кто занял ячейку последним по времени; при совпадении времени берём меньший номер ячейки.

f = open('26-11.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)   # 389 133

Проверка. Ячеек $210$, заявок $987$, успешными оказались $389$ пассажиров. Последняя сдача багажа среди них произошла на $999$-й минуте, и такой пассажир был всего один — он занял ячейку $133$. На типовом примере из условия программа выдаёт $4$ и $1$.

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

Второй вопрос жадность не решает: расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$.

Теперь пара последних мероприятий. Последнее — это любое $j$ с $cnt[j] = K$, а предыдущее — любое совместимое с ним $i$, у которого $cnt[i] = K-1$: тогда цепочка из $K-1$ мероприятий заканчивается на $i$, а $j$ добавляется последним. Перерыв равен разности между началом $j$ и концом $i$, берём наибольший.

f = open('26-12.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)   # 27 4

Проверка. Жадный подсчёт на том же файле тоже даёт $27$ мероприятий. Перерыв вышел совсем небольшим — всего $4$ минуты: заявки в файле плотные, и расписание из $27$ мероприятий почти не оставляет свободы на последнем шаге. На типовом примере из условия программа выдаёт $3$ и $20$.

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

Со вторым вопросом жадность не справляется: она начинает с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому считаем для каждой коробки $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.

Тут работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 3$. Её и находим двоичным поиском, а массив заполняем справа налево.

Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.

from bisect import bisect_left

f = open('26-13-2.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] + 3)   # первая коробка, в которую влезет 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)   # 2767 51

Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $2767$ коробок. Цепочка, стартующая с коробки $51$, действительно содержит $2767$ штук, а если начать со следующей по размеру коробки $52$, выйдет только $2766$. На типовом примере из условия программа выдаёт $3$ и $32$.

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

Второй вопрос жадность не решает: расписаний с максимальным количеством мероприятий много, а перерыв нужен наибольший по всем таким расписаниям. Поэтому считаем динамику: для каждого мероприятия $i$ находим $cnt[i]$ — сколько мероприятий максимум умещается в цепочке, которая заканчивается именно этим. Максимум по всем $cnt$ даёт ответ на первый вопрос, обозначим его $K$.

Теперь пара последних мероприятий. Последнее — это любое $j$ с $cnt[j] = K$, а предыдущее — любое совместимое с ним $i$, у которого $cnt[i] = K-1$: тогда цепочка из $K-1$ мероприятий заканчивается на $i$, а $j$ добавляется последним. Перерыв равен разности между началом $j$ и концом $i$, берём наибольший.

f = open('26-14-2.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)   # 23 19

Проверка. Заявок $990$, жадный подсчёт на том же файле тоже даёт $23$ мероприятия. На типовом примере из условия программа выдаёт $3$ и $20$.

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

Со вторым вопросом жадность не справляется: она стартует с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому для каждой коробки считаем $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.

Работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 11$. Её и находим двоичным поиском, а массив заполняем справа налево.

Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.

from bisect import bisect_left

f = open('26-15-1.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] + 11)   # первая коробка, в которую влезет 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)   # 854 54

Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $854$ коробок. Стартовать можно с любой коробки от $50$ до $54$ — все дают ровно $854$ звена, поэтому в ответ идёт наибольшая из них. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.

Условие «перед ними все кресла с такими же номерами свободны» устроено жёстче, чем в похожей задаче про одно место: там достаточно было свободного участка, а здесь свободными должны быть все ряды от первого. Значит для каждого номера места важна ровно одна величина — номер первого ряда, где это место занято. Обозначим её $first[p]$; если место $p$ не занято нигде, считаем $first[p] = M+1$.

Тогда пара мест $p$ и $p+1$ годится в ряду $r$ при условии $r < first[p]$ и $r < first[p+1]$, то есть $r \le \min(first[p], first[p+1]) — 1$. Обратите внимание, что сюда автоматически входит и требование «сами эти два кресла свободны»: если бы место $p$ было занято в самом ряду $r$, то $first[p] \le r$.

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

Перебирать сами кресла нельзя — их до десяти миллиардов. Массив $first$ имеет размер $K$, и этого достаточно.

f = open('26-16.txt')
N, M, K = map(int, f.readline().split())

first = [M+1] * (K+2)             # первый ряд, где место p занято
for _ in range(N):
    r, p = map(int, f.readline().split())
    if r < first[p]:
        first[p] = r

best_row, best_seat = 0, None
for p in range(1, K):             # пара соседних мест p и p+1
    r = min(first[p], first[p+1]) - 1
    if r > best_row:
        best_row, best_seat = r, p

print(best_row, best_seat)   # 21028 6660

Проверка. В файле $N = 9992$, $M = 99906$, $K = 6661$. Место $6660$ не занято ни в одном ряду, а место $6661$ впервые занято в ряду $21029$. Значит пара работает вплоть до ряда $21028$, и оба кресла в нём свободны. Другой пары с таким же номером ряда нет, так что выбор наименьшего номера места не понадобился. На типовом примере из условия программа выдаёт $5$ и $6$.

Заявки в файле лежат вперемешку, поэтому сначала сортируем их по времени начала приёма — обслуживать граждан надо в порядке обращения. Для каждого окна храним одно число: момент, когда специалист освободится. Гражданин с временем обращения $t$ может попасть в окно, если это число меньше $t$ — так реализуется правило «начиная со следующей минуты после завершения приёма предыдущего».

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

f = open('26-17.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_win = -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_win = t, i + 1
            elif t == last_t and i + 1 < last_win:
                last_win = i + 1
            break

print(cnt, last_win)   # 793 2

Проверка. Окон $267$, заявок $994$, на приём попали $793$ гражданина. Последнее обращение среди них произошло на $1437$-й минуте, и такой гражданин был один — его принял специалист в окне $2$. На типовом примере из условия программа выдаёт $4$ и $1$.

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

Первая часть: студенты без «двоек». Сортируем их по убыванию среднего балла, при равенстве — по возрастанию ID. Средний балл делить на четыре не нужно: сравнение сумм даёт тот же порядок, а с целыми числами не будет проблем с точностью. Чтобы одной сортировкой получить «сумма по убыванию, ID по возрастанию», кладём в ключ сумму со знаком минус.

Вторая часть: студенты с «двойками». Сортируем по количеству «двоек» по возрастанию, при равенстве — по ID. Ровно так и описан порядок в условии: сначала одна «двойка», потом две, три и четыре.

Дальше два ответа. Повышенную стипендию получают первые $N/4$ мест, и по условию гарантируется, что все они попадают в первую часть. Значит нужен элемент рейтинга с номером $N/4$, то есть индекс $N/4 — 1$. Второй ответ — первый в списке студент с более чем двумя «двойками», то есть первый элемент второй части, у которого «двоек» три или четыре.

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

passed, failed = [], []
for _ in range(n):
    v = list(map(int, f.readline().split()))
    sid, marks = v[0], v[1:]
    twos = marks.count(2)
    if twos == 0:
        passed.append((-sum(marks), sid))   # балл по убыванию, ID по возрастанию
    else:
        failed.append((twos, sid))          # число двоек, затем ID

passed.sort()
failed.sort()
rating = [sid for _, sid in passed] + [sid for _, sid in failed]

top = rating[n//4 - 1]                                    # последнее место среди 25 %
first_bad = next(sid for twos, sid in failed if twos > 2)

print(top, first_bad)   # 52326 635

Проверка. Студентов $9964$, из них без «двоек» — $6682$, что заметно больше четверти, так что граница стипендии действительно попадает в первую часть. Четверть мест — это $2491$, и на этом месте стоит студент с ID $52326$ и суммой баллов $17$; соседи по рейтингу имеют ту же сумму, но ID $52268$ и $52380$, то есть тай-брейк по возрастанию ID здесь сработал. С тремя «двойками» в файле $195$ студентов, с четырьмя — $15$, и первый из них по ID — $635$. На типовом примере из условия программа выдаёт $6$ и $13$.

Первая часть — жадность. Отсортируем и грузы, и контейнеры по возрастанию, затем пройдём по контейнерам от меньшего к большему, каждый раз пытаясь положить в него самый лёгкий ещё не упакованный груз. Если он влезает, груз упакован, переходим к следующему. Это даёт максимальное количество, обозначим его $K$.

Вторая часть требует отдельной проверки. Спрашивается не про самый тяжёлый груз какого-то одного оптимального распределения, а про максимально возможный среди всех распределений размера $K$. Идём по грузам от самого тяжёлого к более лёгким и для каждого проверяем: можно ли включить его в распределение, не потеряв в количестве.

Тут важна деталь — какой контейнер отдать кандидату. Отдавать надо наименьший из подходящих, то есть первый контейнер с грузоподъёмностью не меньше массы кандидата. Большие контейнеры полезнее для остальных грузов, поэтому забирать их из общего пула невыгодно. После этого пересчитываем жадность на оставшихся грузах и контейнерах: если получилось ровно $K-1$, кандидат подходит, и это ответ.

from bisect import bisect_left

def match(goods, cans):                      # макс. число упакованных грузов
    i, cnt = 0, 0
    for c in cans:                           # контейнеры по возрастанию
        if i < len(goods) and goods[i] <= c:
            cnt += 1
            i += 1
    return cnt

f = open('26-19.txt')
n, m = map(int, f.readline().split())
goods = sorted(int(f.readline()) for _ in range(n))
cans  = sorted(int(f.readline()) for _ in range(m))

K = match(goods, cans)

best = None
for idx in range(len(goods)-1, -1, -1):      # кандидат на самый тяжёлый груз
    w = goods[idx]
    j = bisect_left(cans, w)                 # наименьший подходящий контейнер
    if j == len(cans):
        continue
    if match(goods[:idx] + goods[idx+1:], cans[:j] + cans[j+1:]) == K - 1:
        best = w
        break

print(K, best)   # 791 197491

Проверка. Грузов $853$ массой от $91534$ до $199595$, контейнеров $796$ грузоподъёмностью от $90045$ до $197604$. Упаковать удаётся $791$ груз. Девять самых тяжёлых грузов, начиная с $198262$, не помещаются ни в один контейнер вообще, поэтому кандидатом становится следующий по массе — $197491$, и для него подходящий контейнер находится. На типовом примере из условия программа выдаёт $4$ и $160$.

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

Первая — моделирование раздела памяти. Держим счётчик накопленного объёма. Для очередного запроса проверяем, влезает ли он: если накопленное плюс новый объём превышает вместимость $K$, сервер сначала делает резервную копию того, что уже лежит в разделе, и обнуляет счётчик, и только потом кладёт туда новый запрос. Обратите внимание на порядок: в копию попадает объём до добавления текущего запроса. В примере это хорошо видно — в $05{:}05{:}05$ копируются $130000$ Кбайт, накопленные первыми двумя запросами, а сам запрос на $90000$ уже начинает новый цикл.

Вторая — суммы по клиентам. Складываем объёмы по идентификаторам, но только для запросов не позднее $11{:}59{:}59$. Время удобно сравнивать прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически, поэтому разбирать его на числа не нужно.

from collections import defaultdict

f = open('26-20.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:                  # свободной памяти не хватает
        backups.append(cur)          # резервная копия накопленного
        cur = 0
    cur += s
    if t <= '11:59:59':              # строки в формате ЧЧ:ММ:СС сравниваются как время
        total[int(c)] += s

backups.sort(reverse=True)
best = max(total, key=lambda c: total[c])

print(best, backups[0] + backups[1])   # 9517 46436

Проверка. В журнале $15005$ записей, вместимость раздела $23218$ Кбайт, резервных копий получилось $1116$. Две наибольшие оказались по $23218$ Кбайт каждая, то есть ровно под завязку, в сумме $46436$. По клиентам до полудня лидирует устройство $9517$ с объёмом $134167$ Кбайт, следующее за ним — $6877$ со $121879$. На типовом примере из условия программа выдаёт $101$ и $252000$.