Задание EGEINF05BFA6: Сортировка, отбор и моделирование

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

В файле N = 4435 коробок, обязательная разность D = 57. Кроме размера нужно учитывать материал: соседние коробки должны иметь разные обозначения 0 и 1. Простое начало с самой большой коробки не гарантирует оптимальную длину при чередовании материалов.

Обрабатываем возможные стороны s по убыванию. Обозначим best[c][s] максимальное количество коробок в цепочке, внутренняя коробка которой имеет материал c и сторону не меньше s. Цепочку удобно наращивать внутрь: если существует коробка размера s и материала c, то снаружи от неё может стоять цепочка с внутренним материалом 1 − c и стороной не меньше s + D.

Поэтому длина лучшей цепочки, заканчивающейся ровно этой коробкой, равна 1 + best[1 − c][s + D]. После вычисления обновляем best[c][s] максимумом нового значения и best[c][s + 1]. Нулевое значение означает отсутствие внешней цепочки. Поскольку D > 0, все зависимости относятся к уже обработанным большим сторонам.

Рассматриваются оба материала и все размеры, поэтому не теряется ни один возможный выбор внешней коробки. Из кандидатов сначала выбираем наибольшую длину, затем наибольшую сторону внутренней коробки. Повторы одинакового размера и материала не увеличивают длину, так что достаточно множеств размеров. При максимальной стороне L время O(N + L + D), память O(L + D).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n, gap = map(int, f.readline().split())
    sizes = [set(), set()]
    for _ in range(n):
        size, material = map(int, f.readline().split())
        sizes[material].add(size)
limit = max(max(group, default=0) for group in sizes)
best = [[0] * (limit + gap + 2) for _ in range(2)]
answer = (0, 0)
for size in range(limit, 0, -1):
    for material in range(2):
        best[material][size] = best[material][size + 1]
        if size in sizes[material]:
            length = 1 + best[1 - material][size + gap]
            best[material][size] = max(best[material][size], length)
            answer = max(answer, (length, size))
print(*answer)

Проверка результата.

Найденная длина 166, внутренняя сторона 63. Фрагмент достигающей ответ цепочки от внутренней коробки к внешней:

Во всей цепочке материалы чередуются, а минимальный прирост стороны равен 57 ≥ 57. Таблица показывает начало и конец; глобальный максимум подтверждён динамическим расчётом для всех размеров.

Ответ: 166 63.