27. Программирование —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#88418

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 180 м $3$ . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные возможные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок c количеством топлива меньше 300.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K ( $1 ≤ N ≤ 10000 000$ , $1 ≤ K ≤ 10000000$ ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

5_27A.txt

5_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’5_27A.txt’)

N, K = map(int, f.readline().split())
b = 180
m = 300
points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, petrol])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += ceil(petrol / b) * min(abs(cur_d - dist), K - abs(cur_d - dist))
    if 0 < cur_p < m:
        costs.append(sm)

print(min(costs))

# Файлик B
from math import ceil

f = open(’5_27B.txt’)

N, K = map(int, f.readline().split())
b = 180
m = 300

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
                                                                                                  
                                                                                                  
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += ceil(points[i] / b) * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum([ceil(i / b) for i in points[-(K // 2):]])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum([ceil(i / b) for i in points[:K // 2]])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if 0 < points[0] < m:
    costs.append(sm)

for i in range(1, K):
    l += ceil(points[i - 1] / b) - ceil(points[-(K // 2) + i - 1] / b)
    r += ceil(points[(K // 2) + i - 1] / b) - ceil(points[i - 1] / b)
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if 0 < points[i] < m:
        costs.append(sm)

print(min(costs))

Ответ: 32293 1541591932779

Ошибка.
Попробуйте повторить позже

Задача 2#88417

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 40 м $3$ . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные возможные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок c количеством топлива более 900.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K ( $1 ≤ N ≤ 10000 000$ , $1 ≤ K ≤ 10000000$ ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

4_27A.txt

4_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’4_27A.txt’)

N, K = map(int, f.readline().split())
b = 40
m = 900
points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, petrol])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += ceil(petrol / b) * min(abs(cur_d - dist), K - abs(cur_d - dist))
    if cur_p > m:
        costs.append(sm)

print(min(costs))

# Файлик B
from math import ceil

f = open(’4_27B.txt’)

N, K = map(int, f.readline().split())
b = 40
m = 900

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
                                                                                                  
                                                                                                  
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += ceil(points[i] / b) * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum([ceil(i / b) for i in points[-(K // 2):]])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum([ceil(i / b) for i in points[:K // 2]])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if points[0] > m:
    costs.append(sm)

for i in range(1, K):
    l += ceil(points[i - 1] / b) - ceil(points[-(K // 2) + i - 1] / b)
    r += ceil(points[(K // 2) + i - 1] / b) - ceil(points[i - 1] / b)
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if points[i] > m:
        costs.append(sm)

print(min(costs))

Ответ: 90063 8222309155254

Ошибка.
Попробуйте повторить позже

Задача 3#88416

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 235 м $3$ . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите разницу между минимальными и максимальными возможными расходами на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K ( $1 ≤ N ≤ 10000 000$ , $1 ≤ K ≤ 10000000$ ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа через пробел: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

3_27A.txt

3_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’3_27A.txt’)

N, K = map(int, f.readline().split())
b = 235

points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, ceil(petrol / b)])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += petrol * min(abs(cur_d - dist), K - abs(cur_d - dist))
    costs.append(sm)

print(max(costs) - min(costs))

# Файлик B
from math import ceil

f = open(’3_27B.txt’)

N, K = map(int, f.readline().split())
b = 235

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
for i in f:
    dist, petrol = map(int, i.split())
                                                                                                  
                                                                                                  
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    petrol = ceil(petrol / b)
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += points[i] * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum(points[-(K // 2):])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum(points[:K // 2])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if points[0] > 0:
    costs.append(sm)

for i in range(1, K):
    l += points[i - 1] - points[-(K // 2) + i - 1]
    r += points[(K // 2) + i - 1] - points[i - 1]
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if points[i] > 0:
        costs.append(sm)

print(max(costs) - min(costs))

Ответ: 9153 5431509579

Ошибка.
Попробуйте повторить позже

Задача 4#88415

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 64 м $3$ . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите максимальные возможные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K ( $1 ≤ N ≤ 10000 000$ , $1 ≤ K ≤ 10000000$ ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа через пробел: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

2_27A.txt

2_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’2_27A.txt’)

N, K = map(int, f.readline().split())
b = 64

points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, ceil(petrol / b)])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += petrol * min(abs(cur_d - dist), K - abs(cur_d - dist))
    costs.append(sm)

print(max(costs))

# Файлик B
from math import ceil

f = open(’2_27B.txt’)

N, K = map(int, f.readline().split())
b = 64

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
for i in f:
    dist, petrol = map(int, i.split())
                                                                                                  
                                                                                                  
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    petrol = ceil(petrol / b)
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += points[i] * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum(points[-(K // 2):])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum(points[:K // 2])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if points[0] > 0:
    costs.append(sm)

for i in range(1, K):
    l += points[i - 1] - points[-(K // 2) + i - 1]
    r += points[(K // 2) + i - 1] - points[i - 1]
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if points[i] > 0:
        costs.append(sm)

print(max(costs))

Ответ: 94536 7662047669831

Ошибка.
Попробуйте повторить позже

Задача 5#88414

На кольцевой автодороге с двусторонним движением находится N бензоколонок (не более одной бензоколонки на каждом километре дороги). Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке. Известно количество топлива, которое ежедневно на каждую бензоколонку доставляет отдельный бензовоз. Для перевозки топлива используются бензовозы вместимостью 25 м $3$ . Стоимость доставки топлива вычисляется как произведение количества рейсов бензовоза на расстояние от нефтехранилища до бензоколонки. Пробег пустого бензовоза не учитывается. Определите минимальные расходы на доставку топлива до всех бензоколонок, если нефтехранилище расположено на кольцевой автодороге на территории одной из бензоколонок.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит два числа: N, K ( $1 ≤ N ≤ 10000 000$ , $1 ≤ K ≤ 10000000$ ) – соответственно количество бензоколонок на кольцевой автодороге и длина автодороги в километрах. В каждой из следующих N строк находятся два числа: номер километра кольцевой автодороги, на котором расположена бензоколонка, и количество топлива в кубометрах (все числа натуральные, количество топлива на каждой бензоколонке не превышает 1000). Данные указаны в порядке расположения бензоколонок на автодороге.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

1_27A.txt

1_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’1_27A.txt’)

N, K = map(int, f.readline().split())
b = 25

points = []
for i in f:
    dist, petrol = map(int, i.split())
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    if dist == K:
        dist = 0
    points.append([dist, ceil(petrol / b)])

costs = []
for cur_d, cur_p in points:
    # Перебираем пункты, где можем поставить нефтехранилище
    sm = 0
    for dist, petrol in points:
        # Для пункта увеличиваем сумму
        # Умножаем расстояние от нефтехранилища до пункта на количество рейсов
        sm += petrol * min(abs(cur_d - dist), K - abs(cur_d - dist))
    costs.append(sm)

print(min(costs))

# Файлик B
from math import ceil

f = open(’1_27B.txt’)

N, K = map(int, f.readline().split())
b = 25

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количество рейсов к конкретному пункту
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет влиять на сумму

points = [0] * K
for i in f:
    dist, petrol = map(int, i.split())
                                                                                                  
                                                                                                  
    # Чтобы рейсов бензовоза хватило, округлять нужно в большую сторону - ceil
    petrol = ceil(petrol / b)
    # Выполняем условие, что K-й километр также является и 0-м
    if dist == K:
        dist = 0
    points[dist] = petrol

points = points * 2

# Изначальная сумма для 0-го пункта
sm = 0
for i in range(1, K):
    sm += points[i] * min(i, K - i)

# Все пункты слева будут удаляться, на их сумму будем увеличивать
l = sum(points[-(K // 2):])
# Все пункты справа будут приближаться, их сумму будем вычитать
r = sum(points[:K // 2])

costs = []
# Первый пункт добавляем только в случае, если там может стоять завод
if points[0] > 0:
    costs.append(sm)

for i in range(1, K):
    l += points[i - 1] - points[-(K // 2) + i - 1]
    r += points[(K // 2) + i - 1] - points[i - 1]
    sm += l - r
    # Пункт добавляем только в случае, если в нём может стоять завод
    if points[i] > 0:
        costs.append(sm)

print(min(costs))

Ответ: 138047 18483087239705

Ошибка.
Попробуйте повторить позже

Задача 6#88162

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 289 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите, насколько изменится минимальную общая стоимость доставки биоматериалов из всех пунктов приёма в лабораторию, если сменить контейнеры на такие, что их обьем не превышает 451.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $7 (1 ≤ N ≤ 10 )$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

7_27A.txt

7_27B.txt

Показать ответ и решение

Чтобы найти разницу между моделями с разными по объёму контейнерами, запустим программы сначала с k=289, а потом с k=451 и вычтем из первого результата второй. Для файла А получим: 348015 - 254631 = 93384 Для файла В получим: 339199669208 - 246528140589 = 92671528619 Эти числа и запишем в ответ.

# Файлик A
from math import ceil

f = open(’7_27A.txt’)
# k = 289
k = 451
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
    points.append([dist, ceil(cnt / k)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(min(costs))


# Файлик B
from math import ceil

f = open(’7_27B.txt’)
# k = 289
k = 451
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
                                                                                                  
                                                                                                  
start = 10 ** 10
end = -1

for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    points[num] = ceil(cnt / k)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
                                                                                                  
                                                                                                  
        costs.append(current_cost)

print(min(costs))

Ответ: 93384 92671528619

Ошибка.
Попробуйте повторить позже

Задача 7#88161

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 300 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. При этом в пункте, в котором располагают лабораторию, количество пробирок должно быть больше 900.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $7 (1 ≤ N ≤ 10 )$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

6_27A.txt

6_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’6_27A.txt’)
k = 300
m = 900
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    points.append([dist, cnt])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
        sm += abs(dist - cur_d) * ceil(cnt / k)
    if cur_c > m:
        costs.append(sm)

print(min(costs))


# Файлик B
from math import ceil

f = open(’6_27B.txt’)
k = 300
m = 900
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
                                                                                                  
                                                                                                  
start = 10 ** 10
end = -1

for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во пробирок
    points[num] = cnt
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += ceil(points[i] / k) * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum([ceil(i / k) for i in points])

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += ceil(points[i - 1] / k)
    right -= ceil(points[i - 1] / k)
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > m:
                                                                                                  
                                                                                                  
        costs.append(current_cost)

print(min(costs))

Ответ: 319539 329243859815

Ошибка.
Попробуйте повторить позже

Задача 8#88160

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов.

Благодаря развитию нанотехнологий и изобретению телепортов компания, расположив в каждом пункте по одному устройству телепортации, может отправлять некоторое количество пробирок напрямую в лабораторию абсолютно бесплатно. Но так как телепортация - новая технология, пока что ещё запускать телепорты можно только раз в день, и перемещать они могут только число пробирок, являющееся факториалами натуральных чисел.

Поэтому компания решила телепортировать из каждого пункта максимально возможное число пробирок, а остальные поштучно доставлять в лабораторию по автомагистрали.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество пробирок. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $7 (1 ≤ N ≤ 10 )$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

5_27A.txt

5_27B.txt

Показать ответ и решение

# Файлик A

# Функция, которая вычитает максимальный подходящий факториал из числа пробирок
def fact(x):
    mx = max([i for i in facts if x >= i])
    return x - mx


# Сначала необходимо сгенерировать факториалы до 1000
facts = [0, 1]
k = 2
while facts[-1] <= 1000:
    facts.append(facts[-1] * k)
    k += 1

f = open(’5_27A.txt’)
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # С поиощью нашей функции fib находим остаток нетелепортированных пробирок
    points.append([dist, fact(cnt)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(min(costs))


# Файлик B

# Функция, которая вычитает максимальный подходящий факториал из числа пробирок
def fact(x):
    mx = max([i for i in facts if x >= i])
    return x - mx

                                                                                                  
                                                                                                  

# Сначала необходимо сгенерировать факториалы до 1000
facts = [0, 1]
k = 2
while facts[-1] <= 1000:
    facts.append(facts[-1] * k)
    k += 1

f = open(’5_27B.txt’)
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    # С поиощью нашей функции fib находим остаток нетелепортированных пробирок
    points[num] = fact(cnt)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

                                                                                                  
                                                                                                  
# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(min(costs))

Ответ: 32102739 33561551011003

Ошибка.
Попробуйте повторить позже

Задача 9#88159

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов.

Благодаря развитию нанотехнологий и изобретению телепортов компания, расположив в каждом пункте по одному устройству телепортации, может отправлять некоторое количество пробирок напрямую в лабораторию абсолютно бесплатно. Но так как телепортация - новая технология, пока что ещё запускать телепорты можно только раз в день, и перемещать они могут только число пробирок, являющееся членами последовательности Фибоначчи.

Поэтому компания решила телепортировать из каждого пункта максимально возможное число пробирок, а остальные поштучно доставлять в лабораторию по автомагистрали.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество пробирок. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $7 (1 ≤ N ≤ 10 )$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

4_27A.txt

4_27B.txt

Показать ответ и решение

# Файлик A

# Функция, которая вычитает максимальное подходящее число фибоначчи из числа пробирок
def fib(x):
    mx = max([i for i in fibs if x >= i])
    return x - mx

# Сначала необходимо сгенерировать числа фибоначчи до 1000
fibs = [0, 1, 1]
while fibs[-1] <= 1000:
    fibs.append(fibs[-2] + fibs[-1])

f = open(’4_27A.txt’)
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # С поиощью нашей функции fib находим остаток нетелепортированных пробирок
    points.append([dist, fib(cnt)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(min(costs))


# Файлик B

# Функция, которая вычитает максимальное подходящее число фибоначчи из числа пробирок
def fib(x):
    mx = max([i for i in fibs if x >= i])
    return x - mx

# Сначала необходимо сгенерировать числа фибоначчи до 1000
fibs = [0, 1, 1]
while fibs[-1] <= 1000:
                                                                                                  
                                                                                                  
    fibs.append(fibs[-2] + fibs[-1])

f = open(’4_27B.txt’)
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    # С поиощью нашей функции fib находим остаток нетелепортированных пробирок
    points[num] = fib(cnt)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
                                                                                                  
                                                                                                  
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(min(costs))

Ответ: 17042792 17209100128563

Ошибка.
Попробуйте повторить позже

Задача 10#88158

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 111 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Компания наняла менеджера, который должен был рассчитать, в каком пункте наиболее выгодно расположить лабораторию - так, чтобы стоимость перевозки за день была минимальна. Но менеджер что-то перепутал и посчитал наоборот самый невыгодный пункт и стоимость получилась максимальной.

Определите, сколько теряет компания из-за менеджера каждый день. Найдите разницу между суммой, что посчитал менеджер и минимальной общей стоимостью доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $7 (1 ≤ N ≤ 10 )$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

3_27A.txt

3_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’3_27A.txt’)
k = 111
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
    points.append([dist, ceil(cnt / k)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(max(costs) - min(costs))


# Файлик B
from math import ceil

f = open(’3_27B.txt’)
k = 111
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

                                                                                                  
                                                                                                  
for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    points[num] = ceil(cnt / k)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(max(costs) - min(costs))

Ответ: 815903 752430057114

Ошибка.
Попробуйте повторить позже

Задача 11#88157

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 500 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Компания наняла менеджера, который должен был рассчитать, в каком пункте наиболее выгодно расположить лабораторию - так, чтобы стоимость перевозки за день была минимальна. Но менеджер что-то перепутал и посчитал наоборот самый невыгодный пункт и стоимость получилась максимальной.

Определите, какую сумму посчитал менеджер. Найдите максимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $(1 ≤ N ≤ 107)$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

2_27A.txt

2_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’2_27A.txt’)
k = 500
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
    points.append([dist, ceil(cnt / k)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(max(costs))


# Файлик B
from math import ceil

f = open(’2_27B.txt’)
k = 500
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

                                                                                                  
                                                                                                  
for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    points[num] = ceil(cnt / k)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(max(costs))

Ответ: 437253 449804330401

Ошибка.
Попробуйте повторить позже

Задача 12#88156

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 38 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число $(1 ≤ N ≤ 107)$ – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

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

В ответе укажите два числа через пробел: сначала значение искомой величины для файла A, затем – для файла B.

Вложения к задаче

1_27A.txt

1_27B.txt

Показать ответ и решение

# Файлик A
from math import ceil

f = open(’1_27A.txt’)
k = 38
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
    points.append([dist, ceil(cnt / k)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(min(costs))


# Файлик B
from math import ceil

f = open(’1_27B.txt’)
k = 38
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

                                                                                                  
                                                                                                  
for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    points[num] = ceil(cnt / k)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

for i in range(len(points)):
    # Умножаем кол-во контейнеров на расстояние до 0-го пункта
    sm += points[i] * i

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(min(costs))

Ответ: 2064099 2047975715381

Ошибка.
Попробуйте повторить позже

Задача 13#87952

В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод.

Мусор до завода доставляет автомобиль, но в него вмещается не более K килограмм мусора за раз.

Стоимость доставки мусора вычисляется как произведение количества необходимых заездов автомобиля до точки и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.

Требуется определить общую сумму цифр всех возможных общих стоимостей доставок мусора со всех точек.

Входные данные:

Первое число N — количество контейнеров для мусора. Второе число K - вместимость автомобиля. Последующие N чисел — количество килограмм мусора, которое производится на точке.

В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.

Вложения к задаче

27A_07_5.txt

27B_07_5.txt

Показать ответ и решение

# Файлик А
from math import ceil

f = open(’27A_07_5.txt’)

N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2
summa = 0
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)
    summa += sum(map(int, str(sm)))

print(summa)


# Файлик B
from math import ceil

f = open(’27B_07_5.txt’)

N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2

sm = 0
for i in range(1, N):
    sm += a[i] * min(i, N - i)

l = sum(a[-(N // 2):])
r = sum(a[:N // 2])

sums = [sm]

for i in range(1, N):
    l += a[i - 1] - a[-(N // 2) + i - 1]
    r += a[(N // 2) + i - 1] - a[i - 1]
    sm += l - r
    sums.append(sm)

                                                                                                  
                                                                                                  
print(sum([sum(map(int, str(i))) for i in sums]))

Ответ: 35840 65261338

Ошибка.
Попробуйте повторить позже

Задача 14#87951

В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод.

Мусор до завода доставляет автомобиль, но в него вмещается не более K килограмм мусора за раз.

Стоимость доставки мусора вычисляется как произведение количества необходимых заездов автомобиля до точки и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.

Требуется определить разницу между максимальной и минимальной возможными общими стоимостями доставки мусора со всех точек.

Входные данные:

Первое число N — количество контейнеров для мусора. Второе число K - вместимость автомобиля. Последующие N чисел — количество килограмм мусора, которое производится на точке.

В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.

Вложения к задаче

27A_07_4.txt

27B_07_4.txt

Показать ответ и решение

# Файлик А
from math import ceil

f = open(’27A_07_4.txt’)

N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2
mn = 10 ** 10
mx = -1
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)
    mn = min(mn, sm)
    mx = max(mx, sm)

print(mx - mn)


# Файлик B
from math import ceil

f = open(’27B_07_4.txt’)

N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2

sm = 0
for i in range(1, N):
    sm += a[i] * min(i, N - i)

l = sum(a[-(N // 2):])
r = sum(a[:N // 2])

sums = [sm]

for i in range(1, N):
    l += a[i - 1] - a[-(N // 2) + i - 1]
    r += a[(N // 2) + i - 1] - a[i - 1]
                                                                                                  
                                                                                                  
    sm += l - r
    sums.append(sm)

print(max(sums) - min(sums))

Ответ: 105136 21626571588

Ошибка.
Попробуйте повторить позже

Задача 15#87950

На каждом километре односторонней кольцевой автодороги расположены дачные участки. Администрация дачного поселения планирует построить теплицы и выращивать в них сельсхоз. продукцию на одном из участков. При этом рассаду для посева разрешается перевозить не менее чем на K километров, и не более чем на M километров. Известен необходимый суточный объём рассады, которую необходимо доставить грузовиком для определённого дачного участка. Гарантируется, что объём рассады не превышает грузоподъёмность грузовика. Стоимость доставки равна сумме расстояния от фабрики до участка и объёма необходимой рассады. Теплицы расположили на таком участке, что при этом общая стоимость доставок удобрений на все участки, находящиеся на удалении от K до M километров, максимальна.

Определите максимальную общую стоимость доставки удобрений из теплиц.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит три числа, разделённые пробелами: N $(1 ≤ N ≤ 10000000)$ – количество дачных участков, K и M – минимальное и максимальное расстояние для перевозки $(1 ≤ K ≤ M ≤ N − 1)$ . В каждой из следующих N строк находится объём рассады (не превышает 5000). Числа указаны в порядке расположения домов на кольцевой автодороге, начиная с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Вложения к задаче

27A_07_3.txt

27B_07_3.txt

Показать ответ и решение

# Файлик А
f = open(’27A_07_3.txt’)

N, K, M = map(int, f.readline().split())
a = [int(i) for i in f] * 2
mx = -1

for i in range(0, N):
    sm = 0
    for j in range(i + K, i + M + 1):
        sm += (j - i) + a[j]
    mx = max(mx, sm)

print(mx)

# Файлик B
f = open(’27B_07_3.txt’)

N, K, M = map(int, f.readline().split())
a = [int(i) for i in f] * 2

sm = 0
for i in range(K, M + 1):
    sm += i + a[i]

sums = [sm]

for i in range(1, N):
    sm += a[i + M] - a[i + K - 1]
    sums.append(sm)

print(max(sums))

Ответ: 41934 2464889

Ошибка.
Попробуйте повторить позже

Задача 16#87949

В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы общая стоимость доставки мусора была минимальной.

Мусор до завода доставляет автомобиль, но в него вмещается не более K килограмм мусора за раз.

Стоимость доставки мусора вычисляется как произведение количества необходимых заездов автомобиля до точки и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.

Нумерация контейнеров происходит от 1 до N. Требуется определить, рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод.

Входные данные:

Первое число N — количество контейнеров для мусора. Второе число K - вместимость автомобиля. Последующие N чисел — количество килограмм мусора, которое производится на точке.

Выходных данные:

Одно число – номер контейнера для мусора рядом с которым стоит расположить перерабатывающий завод.

В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.

Вложения к задаче

27A_07_2.txt

27B_07_2.txt

Показать ответ и решение

# Файлик А
from math import ceil

f = open(’27A_07_2.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)


# Файлик B
from math import ceil

f = open(’27B_07_2.txt’)

N = int(f.readline())
K = int(f.readline())
a = [ceil(int(i) / K) for i in f] * 2

sm = 0
for i in range(1, N):
    sm += a[i] * min(i, N - i)

l = sum(a[-(N // 2):])
r = sum(a[:N // 2])

sums = [sm]

for i in range(1, N):
    l += a[i - 1] - a[-(N // 2) + i - 1]
    r += a[(N // 2) + i - 1] - a[i - 1]
                                                                                                  
                                                                                                  
    sm += l - r
    sums.append(sm)

print(sums.index(min(sums)) + 1)

Ответ: 70 559555

Ошибка.
Попробуйте повторить позже

Задача 17#87948

В городе M расположена кольцевая автодорога длиной N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги в одном из пунктов сборки мусора собираются поставить мусороперерабатывающий завод таким образом, чтобы общая стоимость доставки мусора была минимальной.

Стоимость доставки мусора вычисляется как произведение вместимости пункта сбора и расстояния от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым.

Требуется определить, какая будет минимальная общая стоимость доставки мусора.

Входные данные:

Первое число N — количество контейнеров для мусора. Последующие N чисел — количество килограмм мусора, которое производится на точке.

Выходных данные:

Одно число – минимальная общая стоимость доставки мусора со всех точек.

В ответе укажите два числа через пробел: сначала искомое значение для файла А, затем для файла B.

Вложения к задаче

27A_07_1.txt

27B_07_1.txt

Показать ответ и решение

# Файлик А
f = open(’27A_07_1.txt’)

N = int(f.readline())
a = [int(i) for i in f] * 2
mn = 10 ** 10
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)
    mn = min(sm, mn)

print(mn)

# Файлик B
f = open(’27B_07_1.txt’)

N = int(f.readline())
a = [int(i) for i in f] * 2

sm = 0
for i in range(1, N):
    sm += a[i] * min(i, N - i)

l = sum(a[-(N // 2):])
r = sum(a[:N // 2])

sums = [sm]

for i in range(1, N):
    l += a[i - 1] - a[-(N // 2) + i - 1]
    r += a[(N // 2) + i - 1] - a[i - 1]
    sm += l - r
    sums.append(sm)

print(min(sums))

Ответ: 91738 109292816488427549

Ошибка.
Попробуйте повторить позже

Задача 18#87557

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 41 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи

Входные данные: Даны два входных файла: файл $A$ (27_10A.txt) и файл $B$ (27_10B.txt), каждый из которых содержит в первой строке количество троек $N$ $(1 ≤ N ≤ 1000000)$ . Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих 10000.

В ответе укажите два числа через пробел: сначала значение искомой суммы для файла $A$ , затем для файла $B$ .

Вложения к задаче

27_10A.txt

27_10B.txt

Показать ответ и решение

f = open(’27_10B.txt’)
n = int(f.readline())
s = 0
#массив для хранения минимальных разностей
mr = [1000000000500000000000]*41
for i in range(n):
    #пара чисел из файла
    a, b = map(int, f.readline().split())
    #добавляем к сумме минимальное число из пары
    s += min(a, b)
    d = abs(a-b) #разница между числами в паре
    mr1 = mr[:]   #копия массива минимальных разностей
    #проходимся по всем остаткам от деления на 41
    for j in range(41):
        #если сумма разницы и элемента массива меньше элемента в массиве,
        #обновляем элемент в массиве
        if d + mr1[j] < mr[(d+mr1[j]) % 41]:
            mr[(d+mr1[j]) % 41] = d + mr1[j]
    #если разница меньше элемента в массиве, обновляем элемент
    if d < mr[d % 41]:
        mr[d % 41] = d
#если сумма делится на 41, выводим ее
if s % 41 == 0:
    print(s)
else:# проходимся по всем элементам массива минимальных разностей
    for i in range(41):
    #если сумма с текущим элементом массива делится на 41,
    #выводим это значение
        if (s + mr[i]) % 41 == 0:
            print(s + mr[i])

Ответ: 483759 2596328198

Ошибка.
Попробуйте повторить позже

Задача 19#87556

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на 37 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.

Входные данные: Даны два входных файла: файл A (27_9A.txt) и файл В (27_9B.txt), каждый из которых содержит в первой строке количество пар N $(1 ≤ N ≤ 100000)$ . Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих 10000.

В ответе укажите два числа через пробел: сначала значение искомой суммы для файла $A$ , затем для файла $B$ .

Вложения к задаче

27_9A.txt

27_9B.txt

Показать ответ и решение

f = open(’27_9B.txt’)
n = int(f.readline())
#массив для хранения минимальных сумм
mr = [10000000000] * 37
#начальная сумма для 0 равна 0
mr[0] = 0
for i in range(n):
    a, b, c = list(map(int, f.readline().split()))
    #временный массив для хранения минимальных сумм
    mr1 = [10000000000] * 37
    #проходимся по всем суммам в массиве mr
    for j in range(37):
        #обновляем минимальную сумму для каждого остатка от деления суммы на 37,
        #добавляя к текущей сумме каждое из чисел из тройки и сохраняя минимальность
        mr1[(mr[j] + a) % 37] = min(mr1[(mr[j] + a) % 37], mr[j] + a)
        mr1[(mr[j] + b) % 37] = min(mr1[(mr[j] + b) % 37], mr[j] + b)
        mr1[(mr[j] + c) % 37] = min(mr1[(mr[j] + c) % 37], mr[j] + c)
    #обновляем массив mr новыми минимальными суммами по модулю 37
    mr = mr1.copy()
#выводим минимальную сумму для остатка 0
print(mr[0])

Ответ: 49395 46611305

Ошибка.
Попробуйте повторить позже

Задача 20#87555

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел делилась на 190 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Входные данные: Даны два входных файла: файл A (27_8A.txt) и файл В (27_8B.txt), каждый из которых содержит в первой строке количество пар N $(1 ≤ N ≤ 100000)$ . Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих 10000.

В ответе укажите два числа через пробел: сначала значение искомой суммы для файла $A$ , затем для файла $B$ .

Вложения к задаче

27_8A.txt

27_8B.txt

Показать ответ и решение

f = open(’27_8B.txt’)
n = int(f.readline())
s = [0]#список, в котором мы будем записывать промежуточные суммы на каждом шаге
D = 190#наш делитель
for i in range(n):
    troika = sorted((map(int,f.readline().split())))#считываем текущую строку
    #образуем всевозможные суммы, которые можно сделать на текущей строке с учетом того, что берем ровно два числа
    s = [a + troika[j] + troika[k] for a in s for j in range(len(troika)-1) for k in range(j+1,len(troika))]
    s = {x % D:x for x in sorted(set(s))}.values()
    #Словарь в качестве ключа которого остаток суммы при делении на D и в качестве значения cама сумма.
    #Поскольку x проходится по отсортированному по возрастанию списку s,
    #то максимальные суммы текущей строки с определенным остатком при делении на D
    #перезапишут минимальные суммы текущей строки с таким же остатком при делении на D.
    #Данная конструкция позволяет значительно уменьшить количество значений сумм в списке s,
    #поскольку мы оставляем только максимальные суммы под определенным остатком при делении на D.
    #длина списка s всегда будет меньше или равна D. Сам метод решения называется метод частичных сумм.
print([x for x in s if x % D == 0])#Вывод значения, которое кратно 190

Ответ: 3425320 1004734820