В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы общая стоимость доставки мусора была минимальной.
Мусор до завода доставляет автомобиль, но в него вмещается не более K килограмм мусора за раз.
Стоимость доставки мусора вычисляется как произведение количества необходимых заездов автомобиля до точки и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.
Нумерация контейнеров происходит от 1 до N. Требуется определить, рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод.
Входные данные:
Первое число N — количество контейнеров для мусора. Второе число K — вместимость автомобиля. Последующие N чисел — количество килограмм мусора, которое производится на точке.
Выходных данные:
Одно число – номер контейнера для мусора рядом с которым стоит расположить перерабатывающий завод.
В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.
Решение для пункта А
from math import ceil
f = open(’27A.txt’)
N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2
mn = 10 ** 10
ind = -1
for i in range(0, N):
sm = 0
for j in range(1 + i, N + i):
d = abs(j - i)
sm += a[j] * min(d, N - d)
if sm < mn:
ind = i + 1
mn = sm
print(ind)
Решение для пункта Б
from math import ceil
f = open(’27B.txt’) # Открываем файл
n = int(f.readline()) # Считываем количество контейнеров
k = int(f.readline()) # Считываем вместимость автомобиля
# Считываем количество необходимых заездов автомобиля в каждом пункте
# Используем округление вверх с помощью функции ceil()
a = [ceil(int(i)/k) for i in f]
# Инициализируем начальную стоимость доставки мусора,
# если завод расположен в пункте №1
s = 0 # Прибавляем к сумме средний элемент
for i in range(1,n//2+n%2):
# Добавляем стоимость доставки для пунктов слева и справа
s += a[i]*i + a[-i]*i
# Рассчитываем разницу в стоимости доставки мусора
# при перемещении завода на следующий пункт
d = sum(a) - sum(a[1:n//2+1 + n%2])*2
mn = 100000000000000000000000000000000 # Минимальная стоимость
t = 1 # Задаём исходный 0-ой пункт, как ответ на задачу
for i in range(1,n): # Для каждого пункта проверяем стоимость доставки
s += d # Обновляем текущую стоимость доставки
if s < mn: # Если текущая стоимость меньше минимальной
mn = s # Запоминаем сумму
t = i + 1 # Запоминаем пункт
# Рассчитываем смещение разницы стоимости доставки
# при перемещении завода к следующему пункту
r = a[i%n]*2 - a[(i+n//2)%n]*2
d += r # Обновляем разницу в стоимости доставки
print(t) # Выводим номер пункта, где стоимость доставки минимальна