Question

В магазине для упаковки подарков есть *N* кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку. **Входные данные.**Задание 26

В первой строке входного файла находится число *N* — количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих *N* строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе. Пример входного файла:54340324030Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, то есть количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

В магазине есть N кубических коробок. Подарок упаковывается по принципу матрёшки — одна коробка помещается в другую. Коробку можно поместить в другую, если длина её стороны как минимум на 9 единиц меньше длины стороны другой коробки.

Определите:
1. Наибольшее количество коробок, которое можно использовать для упаковки одного подарка.
2. Максимально возможную длину стороны самой маленькой из этих коробок.

**Входные данные:** первая строка содержит число N (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (натуральные числа, не превышающие 10 000).

**Пример входного файла:**
```
5
43
40
32
40
30
```

При разнице в 9 единиц условию удовлетворяют наборы: {30, 40, 43} или {32, 40, 43}. Ответ: количество коробок — 3, длина стороны самой маленькой — 32.

### РЕШЕНИЕ

Идея решения: отсортировать коробки по убыванию размера и жадно строить цепочку, добавляя каждую следующую коробку, если она на 9 единиц меньше предыдущей.

Алгоритм:
1. Прочитаем размеры всех коробок из файла.
2. Отсортируем их в порядке убывания.
3. Начнём с самой большой коробки и будем последовательно добавлять в цепочку каждую коробку, которая на 9 единиц меньше последней добавленной.
4. Выведем количество коробок в цепочке и размер самой маленькой.

```python
f = open('26.txt')
n = int(f.readline())
boxes = sorted([int(f.readline()) for _ in range(n)], reverse=True)

answer = [boxes[0]]
for box in boxes[1:]:
    if answer[-1] - box >= 9:
        answer.append(box)

print(len(answer), answer[-1])
```

Сложность: $O(n \log n)$ (доминирует сортировка).

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике