Задание №92903: Алгоритмы и программирование
Задание выполняется с использованием прилагаемых файлов. У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Компания планирует открыть лабораторию в одном из имеющихся пунктов. Перевозить биоматериалы разрешается на расстояние не более M . Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 12 штук. Каждый транспортировочный контейнер используется для доставки пробирок только из одного пункта приёма, при этом из каждого пункта приёма может быть доставлено не более одного контейнера с неполной загрузкой. Пункт для лаборатории выбрали таким образом, чтобы количество доставляемых туда контейнеров с пробирками было максимальным. Определите необходимое количество контейнеров для доставки пробирок в эту лабораторию . Входные данные Даны два входных файла (файл A и файл B ), каждый из которых в первой строке содержит два числа N и M (1 N 10 000 000, 1 M 10 000 000) – количество пунктов приёма биоматериалов и максимальное расстояние, на которое разрешено перевозить биоматериалы. В каждой из следующих N строк находятся два числа: номер пункта и количество пробирок, принимаемых на этом пункте за сутки (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль автомагистрали, считая от нулевой отметки. В ответе укажите два числа: сначала значение искомой величины для файла А , затем – для файла B . Типовой пример организации данных во входном файле 6 3 1 100 3 200 6 4 7 3 8 2 10 190 При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 3. В этом случае количество контейнеров в ней составит: 2 + 3 + 1. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Что проверяет это задание
Задание относится к теме «Алгоритмы и программирование». Для решения понадобятся:
- формализация задачи
- построение алгоритма
- проверка граничных случаев
Источник: ФИПИ — открытый банк заданий
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Происхождение задания
- Банк заданий
- ФИПИ — открытый банк заданий
- Организатор
- ФИПИ
- Материалы
- 2 файла
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Алгоритмы и программирование» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 25 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Информатика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Перепутать основание системы счисления.
- Не учесть границы диапазона.
- Проверить алгоритм только на одном примере.