не могу решить задачу из ЕГЭ на метод префиксных сумм. помогите пожалуйста
У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль кольцевой автомагистрали длиной N километров на расстоянии 1 км друг от друга. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью V пробирок. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Для развоза контейнеров к двум соседним пунктам прикреплены две машины, которые, двигаясь в противоположных направлениях, собирают все контейнеры от пункта старта до лаборатории. Из пункта, где располагается лаборатория, стоимость доставки равна нулю. Лабораторию расположили в одном из пунктов приёма таким образом, чтобы стоимость доставки контейнеров у каждой машины была одинакова. Найдите номер пункта, где нужно расположить лабораторию, чтобы стоимость доставки у каждой машины была одинаковая. Если таких пунктов несколько, укажите наибольший номер такого пункта.
Номера пунктов совпадают с порядком в файле и нумеруются с нуля.
Входные данные: Даны два входных файла (файл A и файл B), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) — количество пунктов приёма биоматериалов, и число V (1 ≤ V ≤ 1000) — вместимость транспортировочного контейнера. Каждая из следующих N строк содержит одно натуральное число: количество контейнеров в пункте. Пункты расположены в порядке следования на трассе.
Пример входных данных:
6 10
6
50
25
63
60
39
При таких исходных данных (вместимость транспортировочного контейнера равна 10 пробирок) лабораторию можно открыть в пункте на втором километре (5 + 1⋅2 + 4⋅3 = 7 + 6⋅2) и на пятом километре (6 + 7⋅2 = 1 + 5⋅2 + 3⋅3).
оригинал: https://education.yandex.ru/ege/task/ea729ca3-bf26-46cb-b7d8-1b4b46dd1038
правильные ответы: 27A.txt - 96; 27B.txt - 892584
моё решение (работает при чётном N):
import math
a = open('test.txt')
n, v = map(int, a.readline().split())
a = [math.ceil(int(x) / v) for x in a]
left = suml = right = sumr = 0
length = n // 2
for i in range(1, length):
left += a[-i] * i
suml += a[-i]
right += a[i] * i
sumr += a[i]
if(abs(left - right) == a[length] * length): print(0)
for i in range(1, n):
suml += a[i - 1] - a[i - length]
left += suml - a[i - length] * (length - 1)
right += a[(i + length - 1) % n] * (length - 1) - sumr
sumr += a[(i + length - 1) % n] - a[i]
if(abs(left - right) == a[(i + length) % n] * length): print(i)
проверял его на примере из задачи:
a = [1, 5, 3, 7, 6, 4]
i - позиция лаборатории
left - сумма доставки слева
right - сумма доставки справа
center - стоимость доставки до пункта, который находиться на одинаковом расстоянии от лаборатории, как слева, так и справа
| i | left | right | center |
|---|------|-------|--------|
| 0 | 16 | 11 | 21 |
| 1 | 9 | 17 | 18 |
| 2 | 7 | 19 | 12 |
| 3 | 13 | 14 | 3 |
| 4 | 13 | 6 | 15 |
| 5 | 20 | 11 | 9 |
вроде всё правильно получается (подходят пункты: 2, 5).
но ответ для 27A получается 84, вместо 96
подскажите пожалуйста где я ошибаюсь
заранее спасибо
файл 27A.txt:
100 13
58
94
81
91
74
3
63
95
83
24
60
22
63
39
68
29
86
63
6
104
49
31
46
71
30
55
113
48
103
109
68
71
55
41
71
103
47
71
51
112
96
86
93
22
45
15
6
36
94
88
15
73
61
30
85
8
20
90
86
12
95
88
114
76
81
25
74
38
2
58
45
95
17
101
7
6
56
24
102
17
54
8
46
61
29
38
59
108
2
72
99
12
62
32
60
84
99
52
104
110
Ответы (1 шт):
как сказал homoops ошибка скрывается на 6 строчке, а именно в том что balvan учитывает лишь 2 варианта доставки из n - 1. но если учесть все варианты доставки то можно получить правильный ответ. вот доказательство:
import math
a = open('27B.txt')
n, v = map(int, a.readline().split())
a = [math.ceil(int(x) / v) for x in a]
suml = left = right = sumr = 0
for i in range(1, n):
left += a[-i] * i
suml += a[-i]
start = 0
for i in range(n):
if(i != 0):
start -= 1
right -= sumr
sumr -= a[i]
suml += a[i - 1]
left += suml
mn = abs(left - right)
while(start < n - 1):
start += 1
if(mn < abs(left - a[(i + start) % n] * (n) - right)):
start -= 1
break
suml -= a[(i + start) % n]
left -= a[(i + start) % n] * (n - start)
sumr += a[(i + start) % n]
right += a[(i + start) % n] * start
mn = abs(left - right)
if(mn == 0): print(i)