UOJ Logo LFYZ Online Judge

LFYZOJ

#141. 【NOIP2002 提高组】均分纸牌

Statistics

问题描述

有 $N$ 堆纸牌,编号分别为 $1,2,…, N$。每堆上有若干张,但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌,然后移动。

移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 $N$ 的堆上取的纸牌,只能移到编号为 $N-1$ 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。

例如 $N=4$,4 堆纸牌数分别为:① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的:

  • 从③ 取4张牌放到 ④(9 8 13 10)
  • 从③ 取3张牌放到 ②(9 11 10 10
  • 从② 取1张牌放到①(10 10 10 10)。

输入格式

两行,第一行为一个整数 $N$( $N$ 堆纸牌, $1\leq N\leq 100$)

第二行为 $N$ 个整数 $A_1 A_2 … A_n$ ($N$ 堆纸牌,每堆纸牌初始数,$l\leq A_i\leq 10000$)

输出格式

一行,所有堆均达到相等时的最少移动次数。

样例一

input

4
9 8 17 6

output

3

数据范围与约定

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$