Мусорки, кольцевая дорога —Каталог задач по ЕГЭ - Информатика БУ

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

Задача 1#26694

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

Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

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

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

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

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

Пример входных данных:

$6$

$8$

$20$

$5$

$13$

$7$

$19$

Для данного примера ответ — $6 (7⋅1 + 13⋅2+ 5 ⋅3 + 20⋅2+ 8 ⋅1+ 19⋅0).$

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

Задание_27_B__o4nm.txt

Задание_27_A__o4nh.txt

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

f = open(’27B.txt’)
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]

summa = sum(a)
s = [0]*n
s[0] = sum(a[0:n//2])
for i in range(1,n):
    s[i] = s[i-1]-a[i-1]+a[((i-1)+n//2)%n]

p = [0]*n
for i in range(n):
    p[i] = summa-s[i]

price = [0]*n
for i in range(n//2):
    price[0]+=a[i]*i
for i in range(n//2,n):
    price[0]+=a[i]*(n-i)

mi = 10**20
number = -1
for i in range(1,n):
    price[i] = price[i-1] - s[i] + p[i]
    if price[i]<mi:
        mi = price[i]
        number = i+1
print(number)

Ответ: 16 891102

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

Задача 2#28009

Задание выполняется с использованием прилагаемых файлов

В городе $M$ расположена исследовательская лаборатория сейсмографические датчики которой размещены на окружности на равном расстоянии друг от друга. Каждый датчик несколько раз в сутки отправляет сигнал в центр обработки данных. Количество энергии, необходимое для передачи одного сигнала, пропорционально квадрату расстояния от датчика до ЦОД. Рядом с каким датчиком следует разместить центр обработки данных, чтобы энергия, расходуемая на передачу данных от всех датчиков, была минимальной?

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

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

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

Одно число — номер датчика рядом с которым стоит расположить центр обработки данных.

Пример входного файла:

$7 2$

$5$

$1$

$8$

$3$

$5$

$3$

$7$

Если разместить ЦОД около $5$ -го датчика, то энергия, расходуемая на передачу данных от всех датчиков будет минимальна: $2 2 2 2 2 2 3⋅2 + 3⋅2 + 8⋅4 +7 ⋅4 + 5⋅6 +1 ⋅6 = 480$ .

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

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

Задание_27_A__pstq.txt

Задание_27_B__pstx.txt

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

Решение 1 (неэффективное)

f = open("27A.txt")
n, r = map(int, f.readline().split())
a = [int(f.readline()) for x in range(n)]
ans, place = 100000000, 0

for i in range(n):
    energy = 0
    for j in range(n):
        energy += (min(abs(i - j), n - abs(i - j)) * r) ** 2 * a[j]
    if energy < ans:
        ans = energy
        place = i + 1
print(place)

Решение 2 (эффективное)

f = open(’Задание 27 B.txt’)
n, r = map(int, f.readline().split())
p = n//2
s = [0]*n
a = []
for i in range(n):
    a.append(int(f.readline()))
for i in range(p):
    s[0] += a[i]
for i in range(1, n):
    s[i] = s[i - 1]-a[i - 1]+a[(i - 1 + p) % n]
vvs = [0]*n
for i in range(p):
    vvs[0] += a[i]*(2 * p - 2 * i - 1)
for i in range(1, n):
    vvs[i] = vvs[i - 1] - a[i - 1] * \
        (2 * p - 1) + 2 * s[i] - a[(i - 1 + p) % n]
uvs = [0]*n
for i in range(p):
    uvs[0] += a[i]*(2 * i + 1)
for i in range(1, n):
    uvs[i] = uvs[i - 1] - a[i - 1] + a[(i - 1 + p) % n] * (2*p + 1) - 2 * s[i]
cost = [0]*n
for j in range(n):
    cost[0] += a[j]*(min(j, n - j)*r)**2
for i in range(1, n):
    cost[i] = cost[i-1] + vvs[(i-p) % n]*r**2 - uvs[i]*r**2
print(cost.index(min(cost)) + 1)

Ответ: 19 54841

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

Задача 3#29249

Даны мусорки, расположенные по кругу, в каждой мусорке лежат фантики. Петя и Ваня играют в игру: начинают в диаметрально противоположных точках и с одинаковой скоростью идут в одном направлении по кругу (не навстречу), собирая фантики из мусорок по пути. Каждый соберёт полкруга.

Дано: количество мусорок, позиция Пети, а далее количество фантиков в каждой мусорке.

Вывести: сколько фантиков соберёт Петя, а сколько фантиков соберёт Ваня.

Нумерация мусорок начинается с $0$ .

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

10.txt

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

file = open(’27.txt’, ’rt’)
n = int(file.readline())
p_pos = int(file.readline())
a = [int(file.readline()) for i in range(n)]

v_pos = (p_pos + n // 2) % n
p_sum, v_sum = 0, 0
i = 0
while i < n // 2:
    p_sum += a[(p_pos + i) % n]
    v_sum += a[(v_pos + i) % n]
    i += 1
print(p_sum, v_sum)

Ответ: 14535432 14644943

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

Задача 4#29250

Дано количество мусорок, расположенных по кругу, и количество фантиков во всех этих мусорках. Требуется найти количество фантиков, которое соберёт Петя за половину круга для всех его начальных позиций. Вывести все эти числа от $1$ до $N$ ( $1 ≤ N ≤ 109$ ). В ответе следует записать числа через пробел.

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

11.txt

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

file = open(’27.txt’, ’rt’)
n = int(file.readline())
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i + n // 2 - 1) % n])
print(*s)

Ответ: 710 1045 1402 1669 1334 977

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

Задача 5#29251

В городе $M$ расположена кольцевая автодорога длиной в $N$ километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги около $k$ -ого пункта сборки мусора поставили мусороперерабатывающий завод. Стоимость доставки мусора вычисляется как вместимость пункта сбора, умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с $1$ до $N$ . Требуется найти модуль разницы стоимостей сбора всего мусора при перемещении завода с $k$ -ой позиции контейнера на $k+ 1$ (при $k = N$ , $(k+ 1)$ -ая позиция соответствует $1$ позиции контейнера)

Описание входных данных:

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

Описание выходных данных:

Два числа — модуль разницы стоимостей сбора мусора при перемещении завода с $k$ -ой позиции контейнера на $k+ 1$ (при $k = N$ , $(k+ 1)$ -ая позиция соответствует $1$ позиции контейнера) для обоих файлов через пробел.

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

27_1.txt

27_2.txt

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

file = open(’27-1.txt’, ’rt’)
n = int(file.readline())
k = int(file.readline()) - 1
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

# ищем стоимость, если завод стоит на
# k-ой позиции
price = 0
for i in range(1, n):
    price += min(i, n - i) * a[(i + k) % n]

# найдем k+1 стоимость
new_price = price - s[(k + 1) % n] + p[(k + 1) % n]
print(abs(price - new_price))

Варианты правильных ответов:

64317 135
135 64317

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

Задача 6#29252

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

Описание входных данных:

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

Описание выходных данных:

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

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

13.txt

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

file = open(’13.txt’, ’rt’)
n = int(file.readline())
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

price = 0
for i in range(n // 2):
    price += i * a[i]
for i in range(n // 2, n):
    price += (n - i) * a[i]

minim = price
min_k = -1
for i in range(1, n):
    price -= s[i]
    price += p[i]
    if price < minim:
        minim = price
        min_k = i + 1
print(min_k)

Ответ: 39151

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

Задача 7#30017

Дано количество мусорок, расположенных по кругу, и количество фантиков во всех этих мусорках, требуется найти количество фантиков, которое соберёт Петя за половину круга для всех его начальных позиций. Вывести все эти числа от $1$ до $N$ ( $1 ≤ N ≤ 105$ )

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

garbage1.txt

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

file = open(’garbage1.txt’, ’rt’)
n = int(file.readline())
a = [int(file.readline()) for i in range(n)]
s = [0]*n
s[0] = sum(a[:n // 2])
for i in range(1, n):
    s[i] = s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n]
print(*s)

Ответ: 747 1082 1439 1507 1172 815

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

Задача 8#30018

В городе M расположена кольцевая автодорога длиной в N километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги около k-ого пункта сборки мусора поставили мусороперерабатывающий завод. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора расстояние считается нулевым. Контейнеры нумеруются с 1 до N. Требуется найти модуль разницы стоимостей сбора всего мусора при перемещении завода с k-ой позиции контейнера на k + 1(при k = N, (k + 1)-ая позиция соответствует 1 позиции контейнера)

Описание входных данных:

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

Описание выходных данных:

Одно число — модуль разницы стоимостей сбора мусора при перемещении завода с k-ой позиции контейнера на k + 1(при k = N, (k + 1)-ая позиция соответствует 1 позиции контейнера)

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

garbage2.txt

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

file = open(’garbage2.txt’, ’rt’)
n = int(file.readline())
k = int(file.readline()) - 1
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

# ищем стоимость, если завод стоит на
# k-ой позиции
price = 0
for i in range(1, n):
    price += min(i, n - i) * a[(i + k) % n]

# найдем k+1 стоимость
new_price = price - s[k + 1] + p[k + 1]
print(abs(price - new_price))

Ответ: 64769

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

Задача 9#30019

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

Описание входных данных:

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

Описание выходных данных:

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

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

garbage3.txt

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

file = open(’garbage3.txt’, ’rt’)
n = int(file.readline())
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

price = 0
for i in range(n // 2):
    price += i * a[i]
for i in range(n // 2, n):
    price += (n - i) * a[i]

minim = price
min_k = -1
for i in range(1, n):
    price -= s[i]
    price += p[i]
    if price < minim:
        minim = price
        min_k = i + 1
print(min_k)

Ответ: 39250

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

Задача 10#36820

Дано число $n$ — количество мусорок, расположенных по кругу, затем $n$ чисел — количество фантиков во всех этих мусорках, требуется найти количество фантиков, которое соберёт ИВ, если пройдет по кругу от элемента с номером i до элемента с номером $(n − 2+ i)%n.$ $i$ принимает значения от $0$ до $n− 1$ . ИВ может двигаться только в одну сторону (то есть, ИВ не может разворачиваться и идти собирать фантики в мусорках, которые уже посетил).

Найдите и выведите на экран через пробел все количества фантиков, учитывая все позиции, откуда ИВ может пойти.

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

2.txt

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

f = open("2.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
s = [0] * n
s[0] = sum(a[:n-2+1]) #+1 чтобы учесть n-2ое число

for i in range(1, n):
    s[i] = s[i - 1] - a[i - 1] + a[(n-2+i) % n]
print(*s)

Ответ: 1500 2000 1900 1800 1700 1600

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

Задача 11#36822

Дано число $n$ — количество мусорок, расположенных по кругу, затем $n$ чисел — количество фантиков во всех этих мусорках. Требуется найти количество фантиков, которое соберёт Рома, если пройдет круг от элемента с номером $i$ до элемента с номером $(n∕∕2− 1 + i)%n$ . $i$ принимает значения от $0$ до $n − 1$ . Рома может начинать передвижение по кругу только с мусорок, номера которых четны.

Выведите наибольшее количество фантиков, которое Рома может собрать.

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

3.txt

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

f = open("3.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
s = [0] * n
s[0] = sum(a[:n//2])
for i in range(2, n, 2):
    s[i] = s[i - 2] - a[i - 1] - a[i - 2] + a[(n//2-2+i) % n] + a[(n//2-1+i) % n]
print(max(s))

Ответ: 1200

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

Задача 12#36823

Дано число $n$ — количество мусорок, расположенных по кругу, затем $n$ чисел — количество фантиков во всех этих мусорках, требуется найти количество фантиков, которое соберёт Максим за половину круга для всех его начальных позиций. Вывести все эти числа от $1$ до $N (1 ≤ N ≤ 109)$

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

4.txt

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

f = open("4.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
s = [0] * n
s[0] = sum(a[:n // 2])
for i in range(1, n):
    s[i] = s[i - 1] - a[i - 1] + a[(i + n // 2 - 1) % n]
print(*s)

Ответ: 747 1082 1439 1507 1172 815

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

Задача 13#36824

В городе $M$ расположена кольцевая автодорога длиной в $N$ километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги около $k$ -ого пункта сборки мусора поставили мусороперерабатывающий завод. Стоимость доставки мусора вычисляется, как вместимость пункта сбора умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора расстояние считается нулевым. Контейнеры нумеруются с $1$ до $N$ . Требуется найти модуль разницы стоимостей сбора всего мусора при перемещении завода с $k$ -ой позиции контейнера на $k+ 1$ (при $k = N$ , $(k + 1)$ -ая позиция соответствует 1 позиции контейнера).

Описание входных данных:

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

Описание выходных данных:

Одно число — модуль разницы стоимостей сбора мусора при перемещении завода с $k$ -ой позиции контейнера на $k + 1$ (при $k = N$ , $(k + 1)$ -ая позиция соответствует $1$ позиции контейнера).

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

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

5A.txt

5B.txt

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

f = open("5A.txt")
n = int(f.readline())
k = int(f.readline()) - 1
a = [int(f.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

# ищем стоимость, если завод стоит на
# k-ой позиции
price = 0
for i in range(1, n):
    price += min(i, n - i) * a[(i + k) % n]

# найдем k+1 стоимость
new_price = price - s[k + 1] + p[k + 1]
print(abs(price - new_price))

Ответ: 300 64769

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

Задача 14#36825

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

Описание входных данных:

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

Описание выходных данных:

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

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

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

6A.txt

6B.txt

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

f = open("6A.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i + n // 2 - 1) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

price = 0
for i in range(n // 2):
    price += i * a[i]
for i in range(n // 2, n):
    price += (n - i) * a[i]

minim = price
min_k = 1
for i in range(1, n):
    price -= s[i]
    price += p[i]
    if price < minim:
        minim = price
        min_k = i + 1
print(min_k)

Ответ: 5 39250

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

Задача 15#36826

В городе $M$ расположена кольцевая автодорога длиной в $3⋅N$ километров с движением в обе стороны. На каждом третьем километре установлены контейнеры для мусора. Нулевой километр и $3N$ -й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общая стоимость доставки мусора из всех пунктов в этот центр была минимальной.

Определите минимальные расходы на доставку мусора в центр переработки отходов.

Описание входных данных:

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

Описание выходных данных:

Одно число — минимальные расходы на доставку мусора в центр переработки отходов.

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

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

7A.txt

7B.txt

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

f = open("7B.txt")
n = int(f.readline())
a = [int(f.readline())*3 for i in range(n)]
s = [0] * n
sum = 0
right, left = 0, 0

for i in range(1, n // 2):
    sum += a[i] * i + a[n - i] * i
    right += a[i]
    left += a[n - i]

sum += a[n // 2] * n // 2
s[0] = sum
for i in range(1, n):
    s[i] = s[i - 1] + left + a[i - 1] - right - a[(i + (n // 2) - 1) % n]
    right = right - a[i] + a[(i + (n // 2) - 1) % n]
    left = left - a[(i + (n // 2)) % n] + a[i - 1]
print(min(s))

Ответ: 7932 2323961620665

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

Задача 16#38850

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

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

Контейнеры нумеруются с 1 до $N$ . Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

Описание входных данных:

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

Описание выходных данных:

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

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

27.txt

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

file = open(’1.txt’)
n = int(file.readline())
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

price = 0
for i in range(n // 2):
    price += i * a[i]
for i in range(n // 2, n):
    price += (n - i) * a[i]

minim = price
min_k = -1
for i in range(1, n):
    price -= s[i]
    price += p[i]
    if price < minim:
        minim = price
        min_k = i + 1
print(min_k)

Ответ: 98312

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

Задача 17#38851

В городе $M$ расположена кольцевая автодорога длиной в $N$ километров с движением в обе стороны. На каждом километре автодороги расположены пункты приема мусора определенной вместимости. В пределах кольцевой дороги около $k$ -ого пункта сборки мусора поставили мусороперерабатывающий завод. Стоимость доставки мусора вычисляется как вместимость пункта сбора, умноженная на расстояние от пункта сбора мусора до мусороперерабатывающего завода. Если мусороперерабатывающий завод находится рядом с пунктом сбора, расстояние считается нулевым. Контейнеры нумеруются с 1 до $N$ . Требуется найти модуль разницы стоимостей сбора всего мусора при перемещении завода с $k$ -ой позиции контейнера на $k+ 1$ (при $k = N$ , $(k + 1)$ -ая позиция соответствует 1 позиции контейнера).

Описание входных данных:

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

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

27.txt

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

file = open(’27-1.txt’)
n = int(file.readline())
k = int(file.readline()) - 1
a = [int(file.readline()) for i in range(n)]
s = [sum(a[0:n // 2])]
for i in range(1, n):
    s.append(s[i - 1] - a[i - 1] + a[(i - 1 + n // 2) % n])

summa = sum(a)
p = []
for i in range(n):
    p.append(summa - s[i])

# ищем стоимость, если завод стоит на
# k-ой позиции
price = 0
for i in range(1, n):
    price += min(i, n - i) * a[(i + k) % n]

# найдем k+1 стоимость
new_price = price - s[(k + 1) % n] + p[(k + 1) % n]
print(abs(price - new_price))

Ответ: 800575

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

Задача 18#38852

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

Рядом с каким пунктом сбора мусора нужно поставить мусороперерабатывающий завод?

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

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

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

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

Пример входных данных:

$6$

$8$

$20$

$5$

$13$

$7$

$19$

Для данного примера ответ — $6 (7⋅1 + 13⋅2+ 5 ⋅3 + 20⋅2+ 8 ⋅1+ 19⋅0).$

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

27A.txt

27B.txt

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

f = open(’3B.txt’)
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]

summa = sum(a)
s = [0]*n
s[0] = sum(a[0:n//2])
for i in range(1,n):
    s[i] = s[i-1]-a[i-1]+a[((i-1)+n//2)%n]

p = [0]*n
for i in range(n):
    p[i] = summa-s[i]

price = [0]*n
for i in range(n//2):
    price[0]+=a[i]*i
for i in range(n//2,n):
    price[0]+=a[i]*(n-i)

mi = 10**20
number = -1
for i in range(1,n):
    price[i] = price[i-1] - s[i] + p[i]
    if price[i]<mi:
        mi = price[i]
        number = i+1
print(number)

Ответ: 15 999980

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

Задача 19#38853

На кольцевой автодороге с двусторонним движением находится $N$ заправочных станций. Длина кольцевой автодороги равна $K$ км, нулевой километр и $K$ -й километр находятся в одной точке. Код заправочной станции совпадает с расстоянием этой станции до нулевой отметки дороги в километрах. На заправочные станции нужно ежедневно доставлять бензин из бензохранилища, которое требуется разместить рядом с одной из заправочных станций. Бензин поставляется в цистернах объёмом $V$ м³ каждая, затраты на доставку вычисляются как произведение расстояния на количество цистерн, которые требуются для полной заправки бензоколонок станции (для каждой станции нужно своё количество цистерн, лишь одна цистерна может быть заполнена не полностью). За один рейс бензовоз доставляет бензин только на одну заправочную станцию. Бензохранилище расположено так, чтобы суммарные затраты на доставку бензина были минимальными. Определите минимально возможные суммарные затраты на доставку бензина.

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

Первая строка содержит три числа $N$ , $K$ и $V$ $(1 < N < 10000000,1 < K < 10000000,1 < V < 1000)$ — количество заправочных станций, длина кольцевой автодороги в километрах и объём цистерны.

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

Пример входных данных:

$5$ $11$ $3$

$1$ $8$

$3$ $7$

$5$ $6$

$7$ $5$

$9$ $3$

При таких исходных данных лучше всего расположить бензохранилище около заправочной станции с кодом 3. При этом затраты на доставку бензина составят $2⋅3+ 2 ⋅2 + 4⋅2+ 5 ⋅1 = 23$ .

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

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

27A.txt

27B.txt

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

f = open(’27b.txt’)
n, k, v = map(int, f.readline().split())
a = [0] * k

k_del, ost  = k // 2, k % 2

for i in range(n):
    kilometer_num, kolvo = map(int, f.readline().split())
    a[kilometer_num % k] = kolvo // v + (kolvo % v > 0)

min_sum = 10**25
s = 0
# Считаем минимальную сумму доставки, если завод стоит на нулевом километре
for i in range(1, k):
    s += a[i] * (2*k_del + ost - abs(2*(i-k_del) - ost)) // 2

d = a[0] + sum(a[k_del + 2:k]) - sum(a[1:k_del + 1])

for i in range(1, k):
    s += d
    d += 2 * a[i] - a[(k_del + i) % k] - a[(k_del + i + ost) % k]
    min_sum = min(min_sum, s)
print(min_sum)

Ответ: 1444502 455926219426

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

Задача 20#38854

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

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

В первой строке стоят числа $N,K, V$ и $M$ $(1 < N < 10000000,1 < K < 10000000,1 < V < 10000,1 < M < 10000000)$ — количество жилых домов, длина кольцевой автодороги в километрах и максимальное расстояние, на которое робот может осуществлять доставку почтовых отправлений.

В каждой из следующих $N$ строк находятся два числа: номер километра кольцевой автодороги, на котором расположен жилой дом, и вес ежедневной корреспонденции (все числа натуральные, вес писем и посылок для каждого дома не превышает 1000 кг). Данные указаны в порядке расположения домов на автодороге.

Пример входных данных:

$5$ $11$ $3$ $3$

$1$ $8$

$3$ $7$

$5$ $6$

$7$ $5$

$9$ $3$

При таких исходных данных оптимальное расположение почтового отделения – в доме с номером 3. В этом случае количество пакетов для доставки корреспонденции составит: 3 (для дома 1) + 3 (для дома 3) + 2 (для дома 5) = 8. В дома 7 и 9 почту доставить не удаётся.

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

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

27A.txt

27B.txt

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

f = open(’27b.txt’)
n, k, v, m = list(map(int, f.readline().split()))
a = [0] * k

for i in range(n):
    kilometer_num, pochta = list(map(int, f.readline().split()))
    a[kilometer_num % k] = pochta // v + (pochta % v > 0)

min_s = sum(a)
if m < (k + 1) // 2 - 1:
    c = sum(a[:m*2 + 1])
    if a[m]:
        min_s = c
    else:
        min_s = 0

    for i in range(1, k):
        c += a[(i + m * 2) % k] - a[i - 1]
        if a[(i + m) % k]:
            min_s = max(min_s, c)

print(min_s)

Ответ: 1202 70082

27.02 Мусорки, кольцевая дорога