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

Решение.

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

В файле 10000 коробок. Для этого задания минимальная разность сторон равна 6; значение 3 в иллюстративном примере не заменяет ограничение основного условия.

Отсортируем стороны по убыванию. Внешней выберем самую большую коробку. Затем каждый раз берём наибольшую ещё доступную сторону s, для которой previous − s ≥ 6. Равенство разрешено. Равные стороны не позволяют вложить коробки друг в друга.

Обоснуем оба критерия. Пусть в произвольной допустимой цепочке стороны от внешней к внутренней равны a₁, a₂, …, а жадный выбор даёт g₁, g₂, …. Имеем g₁ ≥ a₁. Если gᵢ ≥ aᵢ, то коробка aᵢ₊₁ подходит внутрь gᵢ, следовательно, наибольшая подходящая сторона gᵢ₊₁ не меньше aᵢ₊₁. По индукции жадная цепочка не короче любой другой.

Для цепочек максимальной длины то же сравнение на последнем шаге даёт максимально возможную сторону внутренней коробки. Поэтому отдельная замена последней коробки не нужна. Сортировка занимает O(N log N), просмотр — O(N), память O(N).

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

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    sizes = sorted((int(f.readline()) for _ in range(n)), reverse=True)
chosen = []
for size in sizes:
    if not chosen or chosen[-1] - size >= 6:
        chosen.append(size)
print(len(chosen), chosen[-1])

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

Получена цепочка из 1511 коробок. Первые стороны снаружи: 9998, 9991, 9984, 9978, 9972. Последние стороны: 82, 76, 66, 60, 54. Минимальная соседняя разность всей цепочки равна 6, что не меньше 6. Последняя сторона 54 максимальна среди цепочек такой длины по доказанному сравнению.

Ответ: 1511 54.