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