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

Решение.
В исходном файле 1_26.txt первая строка содержит количество N, а следующие строки — размеры. Сначала считываем N отдельно, чтобы случайно не принять его за ещё один размер. В нашем файле N = 10000.
Ищем набор максимальной длины; среди таких наборов нужно сделать наименьший размер как можно больше. Допустимый зазор в этой задаче равен 9. Число 3 относится только к иллюстративному примеру и в расчёте по основному файлу не используется.
Отсортируем размеры по убыванию. Возьмём самый большой, затем каждый раз будем выбирать наибольший из оставшихся размеров, который хотя бы на 9 меньше последнего выбранного. Остальные размеры пропускаем. Равенство зазора допустимо: проверяем ≥ 9, а не строгое неравенство.
Одинаковые размеры не могут идти рядом в выбранном наборе, поскольку их разность равна нулю. Если очередной размер не помещается, уменьшать уже выбранный больший элемент не требуется: больший размер оставляет не меньше возможностей для дальнейшего выбора.
Докажем правильность обоих критериев. Пусть g₁, g₂, … — размеры, выбранные алгоритмом, а x₁, x₂, …, xₗ — любой допустимый набор в порядке убывания. Первый жадный выбор g₁ не меньше x₁, поскольку взят максимум файла.
Предположим, что gᵢ ≥ xᵢ. Тогда xᵢ₊₁ ≤ xᵢ − 9 ≤ gᵢ − 9, то есть следующий элемент сравниваемого набора подходит и после gᵢ. Алгоритм выбирает наибольший подходящий размер, поэтому gᵢ₊₁ ≥ xᵢ₊₁.
Значит, алгоритм не может закончиться раньше любого допустимого набора и находит максимальное количество элементов. Для наборов этой максимальной длины L верно также gₗ ≥ xₗ. Именно последний элемент является самым маленьким, поэтому его размер у алгоритма максимально возможен.
Программа на Python 3. Скачанный файл сохраняем рядом с программой под именем 1_26.txt:

with open('1_26.txt', encoding='utf-8-sig') as source:
    n, *sizes = map(int, source.read().split())
assert len(sizes) == n
sizes.sort(reverse=True)
chosen = []
for size in sizes:
    if not chosen or chosen[-1] - size >= 9:
        chosen.append(size)
print(len(chosen), chosen[-1])

Результат выполнения на исходном файле: 1040 57.
Контрольные данные выбранного набора:

Проверка: все 1040 выбранных значений присутствуют в файле, каждое использовано не чаще, чем встречается, и все соседние разности не меньше 9. Если разрешить только размеры строго больше 57, максимальное количество уменьшается до 1039. Следовательно, увеличить длину стороны самого маленького элемента, сохранив 1040 элементов, невозможно. Независимый расчёт максимальной длины для каждого возможного наименьшего размера даёт тот же результат.
Сортировка занимает O(N log N), последующий проход — O(N). Память списка и выбранного набора — O(N).
Ответ: 1040 57.