#P1477. Box of Bricks

    ID: 478 传统题 1000ms 256MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>模拟贪心Southwestern European Regional Contest 1997

Box of Bricks

描述

小鲍勃喜欢玩他的积木盒。他把积木一块一块地叠起来,搭成不同高度的积木堆。"看,我搭了一面墙!"他对姐姐爱丽丝说。"才不是呢,你应该让所有积木堆都一样高。那样才算一面真正的墙。"爱丽丝反驳道。鲍勃想了想,觉得姐姐说得对。于是他开始一块一块地重新摆放积木,使所有积木堆最终高度相同。但懒惰的鲍勃希望移动的积木数量最少。你能帮帮他吗?

输入

输入包含多组数据。每组数据的第一行是一个整数n,表示鲍勃搭的积木堆数量。第二行包含n个数字,表示每堆积木的高度hi。题目保证1 ≤ n ≤ 50且1 ≤ hi ≤ 100。

所有积木的总数可以被积木堆的数量整除。因此,总能通过重新摆放积木使所有堆高度相同。

输入以n = 0结束,该组数据无需处理。

输出

对于每组数据,首先输出数据编号(如样例所示)。然后输出一行"The minimum number of moves is k.",其中k是为了让所有积木堆高度相同所需移动的最少积木数。

每组数据输出后空一行。

样例输入1

6
5 2 4 1 7 5
0

样例输出1

Set #1
The minimum number of moves is 5.

来源

1997年西南欧地区竞赛