Задание №26: Обработка данных с помощью сортировки
Основные типы и прототипы задания №26:
Жадные алгоритмы упаковки файлов
Расписание мероприятий / конференц-залы
Парковка и пассажиры
Условие задания
(Е. Джобс) При перевозке труб для более компактной укладки решено перевозить трубы меньшего диаметра внутри труб большего диаметра. Для каждой трубы известен внешний диаметр D и толщина стенки S (в миллиметрах). Для предотвращения дефекта между трубами оставляют зазор в 3 миллиметра.
Несколько труб, вложенных одна в другую, называют пакетом. Определите максимальное количество труб, которые можно объединить в одном пакете, а также максимальный диаметр самой маленькой трубы в этом пакете.
Входные данные представлены в файле 26-97.txt следующим образом. В первой строке приведено число N – количество труб. В каждой из следующих N строк приведены пары положительных целых чисел: внешний диаметр трубы D и толщина её стенки S.
Пример входного файла:
Входные данные представлены в файле 26-97.txt следующим образом. В первой строке приведено число N – количество труб. В каждой из следующих N строк приведены пары положительных целых чисел: внешний диаметр трубы D и толщина её стенки S.
Пример входного файла:
5При таких исходных данных можно собрать пакет из трёх труб: (100, 5), (80, 3), (62, 5). Ответ: 3 62.
100 5
80 3
74 4
62 5
60 3
Ответ:
36 106