Коробки-матрёшки двух материалов
В магазине для упаковки подарков есть $N$ кубических коробок из материалов двух видов. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $D$ единиц меньше длины стороны другой коробки, при этом любые две соседние коробки сделаны из разных материалов. Известны длины сторон и материалы коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле сначала заданы $N$ и $D$, затем для каждой коробки указаны длина стороны и материал — $0$ или $1$. В ответ запишите два числа: сначала максимальное количество коробок, затем максимально возможную длину стороны самой маленькой коробки. Для решения необходимы данные из прилагаемого входного файла.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Отсортируйте коробки по длине стороны и рассмотрите построение цепочки от меньшей коробки к большей.
2Наводящая — какие числа считатьуровень 2 из 3
Для коробки длины $x$ можно использовать предыдущую коробку длины не больше $x-D$ и другого материала. Храните лучшие результаты отдельно для обоих материалов.
3Прямая — фактически решениеуровень 3 из 3
После сортировки поддерживайте максимальную длину цепочки для каждого материала среди уже обработанных коробок. Для каждой коробки вычисляйте длину цепочки через максимум по противоположному материалу среди коробок с длиной не более $x-D$; при равенстве максимальной длины выбирайте цепочку с большей длиной самой маленькой коробки.