Question

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

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

Ответ:

Accepted Answer

Answer

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

В кондитерской имеется N круглых форм для коржей. Для многоярусного торта каждый верхний корж должен иметь диаметр меньше предыдущего минимум на 4 единицы. Найдите наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, и максимально возможный диаметр самого маленького коржа в таком торте.

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

**Выходные данные:** два целых числа — количество коржей в оптимальной башне и диаметр самого маленького коржа.

**Пример:** для диаметров 43, 40, 32, 40, 30 ответ: 3 32 (последовательность 43 → 40 → 32 или 43 → 40 → 30).

### РЕШЕНИЕ

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

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

```python
f = open('26.txt')
n = int(f.readline())
diameters = [int(line) for line in f]

diameters.sort(reverse=True)

count = 1
min_diameter = diameters[0]

for i in range(1, len(diameters)):
    if min_diameter - diameters[i] >= 4:
        count += 1
        min_diameter = diameters[i]

print(count, min_diameter)
```

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

### ОТВЕТ

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