Задание проверяет умение обрабатывать числовую информацию с использованием сортировки. Оценивается в два первичных балла, время выполнения — 35 минут (согласно спецификации). В демо-варианте 2023 года задание решается быстрее.
Условие задачи
В магазине n³ коробок для упаковки подарков. Упаковка осуществляется по принципу матрёшки: подарок помещается в коробку, затем эта коробка в другую и так далее. Коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Необходимо определить наибольшее количество коробок, которые можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
Входные данные находятся в файле 26.txt. Первая строка содержит число n (количество коробок), которое не используется в решении. Последующие строки содержат n целых чисел – длины сторон коробок.
Алгоритм решения и реализация на Python
Задача эффективно решается на Python. Алгоритм:
- Чтение данных: Файл открывается с помощью контекстного менеджера. Каждая строка файла (кроме первой) преобразуется в целое число и добавляется в список s.
- Сортировка: Список s сортируется по убыванию с помощью sorted(s, reverse=True).
- Поиск количества коробок и минимальной длины: Используется итерация по отсортированному списку. k хранит количество коробок, mini – длину стороны самой маленькой коробки. Перебор начинается со второго элемента (индекс 1). Для каждой коробки проверяется условие: если длина текущей коробки плюс 3 меньше или равна mini, то mini обновляется, а k увеличивается на 1.
- Вывод результата: Выводятся значения k и mini.
with open('26.txt') as f:
s = [int(line) for line in f][1:]
s = sorted(s, reverse=True)
k = 1
mini = s[0]
for i in range(1, len(s)):
if s[i] + 3 <= mini:
mini = s[i]
k += 1
print(k, mini)