Умение выполнять последовательность решения задач анализа данных: сбор первичных данных, очистка и оценка качества данных, выбор и построение модели, преобразование данных, визуализация данных, интерпретация результатов · 9 заданий
- Задание №27№27
Для участников велогонки на каждом километре кольцевой трассыс двусторонним движением установлены пункты питания. Длина кольцевой трассы равна N килом…
Анализ данных
- Задание №27№27
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расс…
Анализ данных
- Задание №27№27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных ч…
Анализ данных
- Задание №27№27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных ч…
Анализ данных
- Задание №27№27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных ч…
Анализ данных
- Задание №27№27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных ч…
Анализ данных
- Задание №27№27
По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует…
Анализ данных
- Задание №27№27
Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся из…
Анализ данных
- Задание №27№27
Задание выполняется с использованием прилагаемых файлов. Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный реш…
Анализ данных
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ꞏ 2 + 3 ꞏ 1 + 5 ꞏ 1 + 6 ꞏ 1 + 8 ꞏ 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Правильный ответ
51063 5634689219329
Пояснение
Решение:
Из пункта с t пробирками уезжает w=⌈t/36⌉ контейнеров: контейнер вмещает не более 36 пробирок и вскрывается только в лаборатории, поэтому «недогруженный» контейнер всё равно нужен. В Python это удобно записать как -(-t // 36).
Если лабораторию открыть в пункте с номером xj, то стоимость доставки равна C(j)=i∑wi∣xi−xj∣. Перебирать все пункты и для каждого считать сумму — это O(N2), для файла B слишком долго. Раскроем модуль: пункты слева от j дают xj∑i<jwi−∑i<jwixi, пункты справа дают ∑i>jwixi−xj∑i>jwi. Пункты в файле уже перечислены в порядке возрастания номера, поэтому, идя по ним слева направо и поддерживая четыре величины — ∑wi и ∑wixi слева и справа, — мы вычисляем C(j) за O(1) для каждого пункта, а весь ответ — за O(N).
def solve(name, cap=36):
f = open(name)
n = int(f.readline())
x = [0] * n # номера пунктов (они же расстояния от нулевой отметки)
w = [0] * n # число контейнеров в пункте
for i in range(n):
a, b = map(int, f.readline().split())
x[i] = a
w[i] = -(-b // cap) # округление вверх: ceil(b / cap)
wt = sum(w)
xwt = sum(w[i] * x[i] for i in range(n))
wl = 0 # сумма весов слева от текущего пункта
xwl = 0 # сумма w*x слева от текущего пункта
best = None
for i in range(n):
wr = wt - wl - w[i]
xwr = xwt - xwl - w[i] * x[i]
cost = x[i] * wl - xwl + xwr - x[i] * wr
if best is None or cost < best:
best = cost
wl += w[i]
xwl += w[i] * x[i]
return best
print(solve('A.txt'), solve('B.txt'))Проверка на примере из условия (вместимость 96): числа контейнеров равны 2,3,1,1,1,2, минимум достигается в пункте 2 и равен 2+0+3+5+6+16=32 — совпадает с пояснением к заданию.Для файла A минимум равен 51063 (лаборатория в пункте 563), для файла B — 5634689219329.Ответ: 51063 5634689219329