Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Table Legs
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 906Accepted: 337

Description

A table with four legs may rock, even on a flat surface, if its legs are not all the same length. Interestingly, regardless of how many legs have differing lengths, it is always possible to saw an amount from some legs so as to make the table sit level on a flat surface without rocking.
Your job is to generalize this approach to a table with many legs equally spaced around the perimeter of a round table. You are to determine the total length of legs to cut so as to have the table sit level without rocking on a flat surface with not necessarily every leg touching the ground.

Input

Input consists of data for a number of tables. For each table, a line will give an integer t, between 3 and 50, indicating the number of legs on the table. t subsequent lines will give, in order around the table's circumference, the lengths of the legs in millimetres. Each leg is perpendicular to the table top. A line containing 0 follows the data for the last table.

Output

Pick a strategy that cuts the least total length from all legs and print this amount as an integer number. Print a blank line between tables.

Sample Input

3
2000
3000
4000
4
2000
2000
1999
2001
5
2000
2000
1999
2001
1999
0

Sample Output

3000

4

1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator