TopCoder problem "PreciousStones" used in TCO08 Round 2 (Division I Level Three)

Problem Statement


Dr. Agnew and Dr. Austin have acquired a bag of stones, each containing some amount of silver and gold. Dr. Agnew is only interested in the silver contained in the stones, while Dr. Austin is only interested in the gold. Using their sophisticated instruments, they have measured the value of the silver and gold in each stone. They want to divide the stones between them, cutting some if necessary, in such a way that they each get the same value of the element they are interested in, and that that value is as high as possible.

Given the value of silver and gold in each stone, determine the highest value that both Dr. Agnew and Dr. Austin can receive of the element they want. Assume that each element is distributed uniformly within each stone, so that if they cut a stone in two parts, each part will have the same ratio of elements as did the whole stone. Between them they must take all of the stones, without throwing any out.

The value of the precious elements in each stone will be given as two int[]s, silver and gold, where silver[i] and gold[i] give the value of the silver and gold, respectively, in stone i.



Parameters:int[], int[]
Method signature:double value(int[] silver, int[] gold)
(be sure your method is public)


-The returned value must be accurate to within a relative or absolute value of 1e-9.


-silver and gold will each contain between 1 and 50 elements, inclusive.
-silver and gold will contain the same number of elements.
-Each element of silver and gold will be between 0 and 100, inclusive.


{ 10, 6 }
{ 3, 10 }
Returns: 10.0
If Dr. Agnew takes the first stone and Dr. Austin takes the second, they can each get a value of 10.
{ 30 }
{ 15 }
Returns: 10.0
They cut the stone into pieces of size 1/3 and 2/3. Dr. Agnew takes the smaller piece (value = 30*1/3 = 10) and Dr. Austin takes the larger piece (value = 15*2/3 = 10).
{ 0, 0 }
{ 10, 11 }
Returns: 0.0
There is no silver. The only way for each person to get an equal value is for Dr. Agnew to take both stones.
{ 3, 5, 4 }
{ 3, 5, 4 }
Returns: 6.0
There are multiple ways for each doctor to get a value of 6. One way is for both of them to take half of each stone.
{ 1, 2, 3 }
{ 2, 2, 2 }
Returns: 3.5
{ 11, 9, 13, 10 }
{ 8, 14, 17, 21 }
Returns: 28.304347826086957

Problem url:

Problem stats url:




PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Greedy, Math, Search