0180. Спички детям

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

У Пети есть N*k (1 ≤ N ≤ 15000) спичек, разложенных по N выложенным в ряд коробкам. Петя хочет, чтобы во всех коробках было одинаковое количество спичек. Для этого он может переложить спичку в соседний коробок. За сколько таких операций он может добиться желаемой конфигурации?

Формат входного файла

В первой строке записано N. Во второй строке записано N чисел, не превосходящих 10⁹ – количество спичек в коробках (первое число – количество спичек в первом коробке, второе – во втором и т.д.).

Формат выходного файла

Выведите минимальное количество операций до достижения желаемой конфигурации.

Пример:

input.txt	output.txt
6 1 6 2 5 3 7	12

Источник: Petrozavodsk Summer 2002. Saratov SU Contest, Tuesday, July 11

Обсудить       Отправить решение



Версия для печати