Задача №2883. Swimming pool
В бассейне плавает \(S\) людей.
В какой-то момент тренер обратил внимание на неравномерное распределение людей по дорожкам бассейна, что вызывает неудобство у посетителей. Для хорошего распределения пловцов необходимо, чтобы их количество на соседних дорожках отличалось не более чем на 1. Но каждое пересечение разделительных поплавков между дорожками увеличивает дискомфорт пловцов. Например, пустая дорожка может быть рядом с пустой или с дорожкой на которой только один пловец.
Ваша задача состоит в том, чтобы минимизировать дискомфорт, возникающий при перемещении с дорожки на дорожку и добиться хорошего распределения посетителей в бассейне.
Первая строка содержит единственное целое число \(N\) – количество дорожек \((1 \le N \le 400)\). Следующая строчка содержит \(N\) чисел, разделённых пробелами. \(i\)-ое число описывает количество пловцов на \(i\)-ой дорожке. Сумма этих чисел \(S (0 \le S \le 1500)\).
Выведите одно целое число - минимальное возможное количество пересечений дорожек, необходимых для достижения хорошего распределения пловцов в бассейне.
В первой группе тестов \(N\) не превосходят 15, она оценивается в 40 баллов.
Во второй группе тестов \(S\) не превосходит 400, дополнительные ограничения на \(N\) отсутствуют, она оценивается в 25 баллов при условии прохождения всех тестов первой группы.
Во третьей группе тестов дополнительные ограничения отсутствуют, она оценивается в 35 баллов при условии прохождения всех тестов первой и второй групп.
3 8 0 2
5
3 8 5 7
1