Задание 27 ЕГЭ по информатике · 69BBBF
Размещение на кольцевой трассеВысокаяКЭС 3.2КЭС 3.16
Для участников велогонки на каждом километре кольцевой трассы с двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N километров. Нулевой и N-й километры трассы находятся в одной точке. Известно количество комплектов питания в каждом из пунктов на трассе. В каждый пункт комплекты питания доставляет отдельный электрокар. Стоимость доставки питания вычисляется как произведение количества комплектов питания на расстояние от мобильного цеха их подготовки до пункта питания спортсменов на трассе. Мобильный цех подготовки комплектов расположен в одном из пунктов питания на трассе таким образом, что общая стоимость доставки из цеха во все пункты минимальна.
Определите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Дано два входных файла — файл A и файл B. Каждый файл в первой строке содержит число N (1≤N≤10 000 000) — количество пунктов питания на кольцевой трассе. В следующих N строках находятся количества комплектов питания в пунктах. Все числа натуральные, количество комплектов в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения на трассе, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем для файла B. Для файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных положений цеха.
1_69BBBF.zipОпределите минимальную суммарную стоимость доставки питания для спортсменов из цеха его подготовки в пункты питания на трассе.
Дано два входных файла — файл A и файл B. Каждый файл в первой строке содержит число N (1≤N≤10 000 000) — количество пунктов питания на кольцевой трассе. В следующих N строках находятся количества комплектов питания в пунктах. Все числа натуральные, количество комплектов в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения на трассе, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем для файла B. Для файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных положений цеха.
Показать ответ
141530; 18192010182272
Подсказки (3)
- Для каждого положения цеха стоимость равна сумме произведений количества комплектов на кратчайшее расстояние по кольцу.
- Разбейте пункты относительно выбранного положения на левую и правую части. Для быстрого вычисления сумм используйте префиксные суммы количеств комплектов и их позиций.
- Для каждого пункта k вычисляйте расстояния до пунктов на дугах длиной не более ⌊N/2⌋. Стоимость всех положений можно получить за O(N) после построения префиксных сумм; выберите минимальное значение.
Решение
1. Пусть пункты пронумерованы от 0 до N−1, а в пункте i находится ai комплектов. Если цех расположен в пункте k, расстояние до пункта i равно min(∣i−k∣,N−∣i−k∣).
2. Стоимость положения k равна F(k)=∑i=0N−1aimin(∣i−k∣,N−∣i−k∣). Прямой перебор всех пар имеет сложность O(N2) и не подходит для файла B.
3. Разделите кольцо относительно пункта k на дуги, расстояния на которых равны последовательным значениям 1,2,…,⌊N/2⌋. С помощью префиксных сумм ∑ai и ∑iai стоимость каждой дуги вычисляется за O(1).
4. Последовательно рассмотрите все N возможных положений цеха, вычисляя стоимость каждого положения по формулам для соответствующих циклических диапазонов. Минимальная из полученных стоимостей является ответом для одного файла.
5. Тот же алгоритм примените отдельно к файлам A и B. Его сложность составляет O(N) по времени и O(N) по памяти либо O(1) дополнительной памяти при потоковой реализации с хранением необходимых сумм.
2. Стоимость положения k равна F(k)=∑i=0N−1aimin(∣i−k∣,N−∣i−k∣). Прямой перебор всех пар имеет сложность O(N2) и не подходит для файла B.
3. Разделите кольцо относительно пункта k на дуги, расстояния на которых равны последовательным значениям 1,2,…,⌊N/2⌋. С помощью префиксных сумм ∑ai и ∑iai стоимость каждой дуги вычисляется за O(1).
4. Последовательно рассмотрите все N возможных положений цеха, вычисляя стоимость каждого положения по формулам для соответствующих циклических диапазонов. Минимальная из полученных стоимостей является ответом для одного файла.
5. Тот же алгоритм примените отдельно к файлам A и B. Его сложность составляет O(N) по времени и O(N) по памяти либо O(1) дополнительной памяти при потоковой реализации с хранением необходимых сумм.
Частые ошибки
- Использовать обычное расстояние по прямой вместо кратчайшего расстояния по кольцу.
- Перебирать все пары «положение цеха — пункт питания», получая сложность $O(N^2)$.
- Забыть учесть циклический переход от пункта $N-1$ к пункту $0$.
- Переполнить 32-битный целочисленный тип при вычислении суммарной стоимости.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 0B12A627Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их…Кластеры точек и звёзд · 0D9B7C27На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары…Программа и описание алгоритма · 195BE627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 233FD127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 267752
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.