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

Решение.
Сначала максимизируем количество вложенных коробок. Среди наборов с этим количеством нужно получить наибольшую сторону самой маленькой коробки. Разность сторон соседних коробок должна быть не меньше 3, равенство 3 допустимо.
Отсортируем длины сторон по убыванию. Начнём с самой большой коробки. Далее каждый раз берём самую большую ещё не выбранную коробку, которая хотя бы на 3 меньше последней выбранной. Так строим цепочку от внешней коробки к внутренней.
Обоснуем выбор. Пусть стороны произвольной допустимой цепочки по убыванию равны b₁, b₂, …, а нашего набора — a₁, a₂, … . Очевидно, a₁ ≥ b₁, потому что первой взята самая большая коробка.
Если aᵢ ≥ bᵢ, то bᵢ₊₁ ≤ bᵢ − 3 ≤ aᵢ − 3. Значит при выборе следующей коробки существует допустимая сторона хотя бы bᵢ₊₁. Мы выбираем наибольшую доступную, поэтому aᵢ₊₁ ≥ bᵢ₊₁. По индукции наш алгоритм может построить цепочку не короче любой другой. Следовательно, её длина максимальна.
То же сравнение для последнего элемента показывает: среди цепочек максимальной длины последняя выбранная сторона максимально возможная. Поэтому второй ответ получается сразу, отдельная замена внутренней коробки не нужна.
Программа на Python 3:

Перед запуском сохраните скачанный файл под именем 26.txt рядом с программой.

with open('26.txt') as source:
    n = int(source.readline())
    sizes = [int(line) for line in source]
assert len(sizes) == n
sizes.sort(reverse=True)
count = 0
last = None
for size in sizes:
    if last is None or last - size >= 3:
        count += 1
        last = size
print(count, last)

В файле 10000 коробок. Получена цепочка из 2767 коробок, сторона самой маленькой равна 51.
Проверка крайних участков цепочки:

Все соседние разности во всей цепочке не меньше 3. На примере из условия алгоритм выбирает 43, 40, 32: ответ 3 и 32; вторую коробку размера 40 использовать нельзя.
Независимое динамическое программирование по возможным длинам сторон подтвердило максимальную длину 2767 и максимальную внутреннюю сторону 51. Сортировка требует O(N log N) времени, последующий проход O(N), память O(N).
Ответ: 2767 51.