CandyMaking
SRM 629 · 2014-07-26 · by dreamoon
Problem Statement
Alice likes making candy. Recently, she promised to make candy for all her classmates. Alice has N classmates. We will number them 0 through N-1, inclusive.
Each of the classmates brought Alice one container for the candy.
Each of the classmates also has a desired total weight of their candy.
You are given this information as two
Alice has promised to fill all containers with candy completely. However, she only has the time to make one type of candy, with constant density. This means that she might be unable to meet the exact desired weights of candy.
Alice now needs to choose the density of the candy she is going to make. In order to make everyone as happy as possible, Alice decided that she wants to minimize the sum of differences between desired and actual weights. In other words: For each classmate, we compute the positive difference between the desired and actual weight of candy they received. Then, we sum all those differences. Alice needs to choose the density of her candy so that this sum becomes as small as possible.
Compute and return the minimum sum of differences between desired and actual weights.
Notes
- Your return value must have an absolute or a relative error at most 1e-9.
Constraints
- N will be between 1 and 50.
- containerVolume and desiredWeight will each contain exactly N elements.
- Each element of containerVolume and desiredWeight will between 1 and 1,000,000, inclusive.
{5}
{1000}
Returns: 0.0
There is one classmate. Her container has 5 liters and she expects 1000 grams of candy. Alice should choose the density of 200 grams per liter. The sum of differences between desired and actual weights is 0.
{10,10}
{1000,2000}
Returns: 1000.0
There are two classmates. They have a 10-liter container each. However, one of them wants 1000 grams of candy and the other wants 2000 grams. There is no way for Alice to satisfy both of them exactly. (Note that she must always fill all containers completely.) There are multiple optimal choices for the density. For these choices, the sum of differences between desired and actual weights is 1000.
{10,20,40}
{4000,2000,1000}
Returns: 5250.0
{1234,1541,3321,1234,123,123,3414,123,12,2442,1421,1223,3232,1123,2121}
{3213,1231,232143,44312,132132,142424,123123,41341,41244,21312,232131,2312,2322,11,2223}
Returns: 983673.2727272725
{30621,30620,2}
{1,1,1000000}
Returns: 999999.9999673415
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CandyMaking with a public method double findSuitableDensity(vector<int> containerVolume, vector<int> desiredWeight) · 69 test cases · 2 s / 256 MB per case