В задании проверяется умение писать программы для анализа числовых последовательностей. За правильный алгоритм, работающий для одного файла, начисляется один балл; за алгоритм, работающий для двух файлов — два балла. На выполнение отводится около 40 минут.
Условие задачи
У медицинской компании N пунктов приёма биоматериалов, расположенных вдоль автомагистрали. Номер пункта соответствует расстоянию от нулевой отметки. Известно количество пробирок, ежедневно принимаемых в каждом пункте. Пробирки перевозят в контейнерах вместимостью не более 36 штук. Контейнер упаковывается в пункте приёма и вскрывается в лаборатории. Стоимость перевозки — произведение расстояния от пункта до лаборатории на количество контейнеров. Общая стоимость перевозки — сумма стоимостей перевозок из каждого пункта. Лабораторию нужно расположить в одном из пунктов так, чтобы общая стоимость доставки была минимальной. Необходимо определить минимальную общую стоимость доставки биоматериалов.
Даны два файла: файл А и файл В.
Файл А:
- Первая строка содержит число N (количество пунктов).
- Последующие строки содержат номер пункта и количество пробирок в этом пункте.
Алгоритм решения для файла А (перебор)
Для решения задачи перебором создадим список, где каждый элемент — подсписок из двух чисел: номер пункта и количество контейнеров. Количество контейнеров вычисляется как $lceil frac{text{количество пробирок}}{36} rceil$.
Этапы алгоритма:
- Чтение файла: Открываем файл, считываем первую строку (N), преобразуем в целое число. Создаём список data.
- Обработка строк: Перебираем строки файла (кроме первой). Разделяем каждую строку по пробелу (x.split()), преобразуем полученные числа в целые (int()). Первое число — номер пункта, второе — количество пробирок.
- Вычисление количества контейнеров: Если количество пробирок кратно 36, количество контейнеров равно количеству пробирок, делённому на 36. Иначе, добавляем 1. Добавляем в data подсписок с номером пункта и количеством контейнеров.
- Расчёт стоимости: Перебираем все пункты (вложенный цикл). Для каждой пары пунктов вычисляем расстояние (модуль разности номеров пунктов), умножаем на количество контейнеров и суммируем.
- Поиск минимума: Инициализируем переменную min_c большим значением (например, 1030). В циклах сравниваем текущую стоимость с min_c и обновляем min_c при необходимости.
- Вывод результата: Выводим значение min_c.
Этот алгоритм гарантирует получение хотя бы одного балла, но для файла В он будет слишком медленным.
Алгоритм решения для файла В (эффективный алгоритм)
Для файла В необходим более эффективный алгоритм, избегающий полного перебора. Идея заключается в вычислении стоимости, начиная с одного пункта и изменяя её при перемещении лаборатории.
Этапы алгоритма:
- Вычисление начальной стоимости: Вычисляем стоимость для лаборатории в первом пункте.
- Создание списка left: Создаём список left длиной N, где left[i] — суммарное количество контейнеров до i-го пункта (включительно).
- Вычисление стоимости для других пунктов: Перебираем пункты, начиная со второго. Для каждого пункта добавляем к текущей стоимости произведение расстояния до предыдущего пункта и разницы количества контейнеров (left[i] — left[i-1]).
- Поиск минимума: Находим минимальную стоимость среди всех вычисленных.
- Вывод результата: Выводим минимальную стоимость.
Этот алгоритм значительно быстрее перебора, так как требует меньшего количества вычислений.
Задание 27 ЕГЭ по информатике — сложная задача, требующая написания алгоритма анализа числовых последовательностей. Для файла А достаточно переборного алгоритма, для файла В необходим эффективный алгоритм, использующий принцип динамического программирования. Решение задачи перебором гарантирует получение хотя бы одного балла.