1480 - Celebrity Split
Time Limit : 100 Second
Memory Limit : 64 MB
Submission: 46
Solved: 20
- Description
Jack and Jill have decided to separate and divide their property equally. Each of their N mansions has a value between 1,000,000 and 40,000,000 dollars. Jack will receive some of the mansions; Jill will receive some of the mansions; the remaining mansions will be sold, and the proceeds split equally.
Neither Jack nor Jill can tolerate the other receiving property with higher total value. The sum of the values of the mansions Jack receives must be equal to the sum of the values of the mansions Jill receives. So long as the value that each receives is equal, Jack and Jill would like each to receive property of the highest possible value.
Given the values of N mansions, compute the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.- Input
- Suppose Jack and Jill own 5 mansions valued at 6,000,000, 30,000,000, 3,000,000, 11,000,000, and 3,000,000 dollars. To satisfy their requirements, Jack or Jill would receive the mansion worth 6,000,000 and the other would receive both manstions worth 3,000,000 dollars. The mansions worth 11,000,000 and 30,000,000 dollars would be sold, for a total of 41,000,000 dollars. The answer is therefore 41000000.
- Output
- For each test case, output a line containing a single integer, the value of the mansions that must be sold so that the rest may be divided so as to satisfy Jack and Jill.
- sample input
-
5 6000000 30000000 3000000 11000000 3000000 0
- sample output
-
41000000
- hint
- source
- waterloo 26 Septemeber, 2010