Задание EGEINF494D7D: Эффективная обработка данных и кластеры

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 100 записей, в файле B — 1100000. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

Вместимость контейнера c = 40. Для пункта с t пробирками нужно w = ⌈tc⌉ контейнеров. В программе divmod даёт целую часть и остаток; прибавляем один, если остаток положителен. Округляем каждый пункт отдельно: объединять остатки из разных пунктов нельзя. Позиции x уже упорядочены по дороге.

Стоимость для лаборатории в x равна F(x) = Σ wᵢ · |xᵢ − x|. Если сдвинуть её вправо между соседними пунктами на d, стоимость изменится на d · (Wлев − Wправ): путь слева удлинится, справа укоротится. Поэтому стоимость убывает, пока справа больше половины всех контейнеров, и возрастает, когда слева больше половины.

Выбираем первый пункт, где накопленная сумма контейнеров не меньше половины общей: проверяем 2 · накопленная ≥ общая без округления. В этой взвешенной медиане с каждой строгой стороны не больше половины веса; это обеспечивает минимум. При равенстве возможен целый промежуток минимумов, но выбранный существующий пункт допустим. После выбора позиции один раз суммируем wᵢ · |xᵢ − x|. Пробирки самого пункта дают нулевую стоимость.

Распакуем архив и положим указанные в программе текстовые файлы рядом с ней. Программа печатает результат для A, затем для B:

from array import array

def solve(name):
    capacity = 40
    x = array("q")
    w = array("q")
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        for _ in range(n):
            position, tubes = map(int, f.readline().split())
            quotient, remainder = divmod(tubes, capacity)
            x.append(position)
            w.append(quotient + (remainder > 0))

    total = sum(w)
    accumulated = 0
    for i, weight in enumerate(w):
        accumulated += weight
        if 2 * accumulated >= total:
            center = x[i]
            break
    return sum(weight * abs(position - center) for position, weight in zip(x, w))

print(solve('313_27_A.txt'), solve('313_27_B.txt'))

Время O(N), память O(N). Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Удвоенный вес каждой строгой стороны не превосходит общего веса. Прямая сумма стоимости по всем пунктам даёт число в последнем столбце; независимый пересчёт изменений стоимости между соседними пунктами подтверждает минимум.

Ответ: 57616 4608391320516.