Question

В магазине для упаковки подарков есть *N* кубических коробок красного цвета и *M* кубических коробок зеленого цвета ![ левая круглая скобка N больше M правая круглая скобка .](https://ege.sdamgia.ru/formula/svg/92/92ca1c66b08f90492ecb3191a94afa2d.svg) Самой интересной считается упаковка подарка по принципу матрешки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 5 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.**Входные данные**: Задание 26

В первой строке входного файла находятся число *N* — количество коробок красного цвета в магазине (натуральное число, не превышающее 10 000) и через пробел число *M* — количество коробок зеленого цвета в магазине (натуральное число, не превышающее 10 000). В следующих *N* строках находятся значения длин сторон коробок красного цвета (все числа натуральные, не превышающие 10 000) и через знак табуляции значения длин сторон коробок зеленого цвета (все числа натуральные, не превышающие 10 000 ), каждая пара таких значений в отдельной строке; в последних *N* – *M* строках второе число опускается, и числа, соответствующие длинам сторон коробок красного цвета, идут каждое в отдельной строке.Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.Типовой пример организации данных во входном файле:5 439 5540 4244 4440 5550Пример входного файла приведён для случая пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных ответом будет являться 4, 40.

Ответ:

Accepted Answer

Answer

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

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

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

**Входные данные:**
- Первая строка: $N$ и $M$ (натуральные числа, не превышающие 10 000).
- Следующие $M$ строк: пары чисел (длина красной коробки, длина зелёной коробки), разделённые табуляцией.
- Последующие $N - M$ строк: только длины красных коробок.

Все длины — натуральные числа, не превышающие 10 000.

**Пример входного файла:**
```
5 4
39 55
40 42
44 44
40 55
50
```

При минимальной разнице 5 единиц ответ: **4 40**.

### РЕШЕНИЕ

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

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

```python
f = open("2681493.txt")
n, m = map(int, f.readline().split())

boxes = []

for i in range(m):
    red_box, green_box = map(int, f.readline().split())
    boxes.append([red_box, 'red'])
    boxes.append([green_box, 'green'])

for i in range(n - m):
    red_box = int(f.readline())
    boxes.append([red_box, 'red'])

boxes.sort(reverse=True)

present = [boxes[0]]

for box in boxes:
    if present[-1][0] - box[0] >= 5:
        if present[-1][1] != box[1]:
            present.append(box)

print(len(present), present[-1][0])
```

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

### ОТВЕТ

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