CakesEqualization
SRM 421 · 2008-10-07 · by ivan_metelsky
Problem Statement
You are organizing a party and have bought several pieces of cake for it. The weights of these pieces are given in the
After looking at the pieces more carefully, you became worried that they have different weights and decided to make these differences smaller. In order to do this, you can make at most maxCuts cuts. With each cut you can choose one of the pieces you currently have and divide it into two distinct pieces. Note that each of these two pieces can be chosen again when making subsequent cuts.
Your goal is to produce cuts in such way that the difference between the maximal and the minimal pieces' weights becomes as small as possible. Find the best way of making cuts and return the optimal difference.
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- weights will contain between 1 and 50 elements, inclusive.
- Each element of weights will be between 1 and 1,000,000,000, inclusive.
- maxCuts will be between 1 and 100,000, inclusive.
{1, 3}
2
Returns: 0.0
First, choose the piece with weight 3 and cut it into pieces with weights 1 and 2. Then, choose the piece with weight 2 and cut it into two pieces with weight 1. Now all pieces have the same weight, so the answer is 0.
{1, 1, 1, 1, 1}
4
Returns: 0.0
Even though you are allowed to make 4 cuts, there is no sense in making any of them.
{1, 3}
1
Returns: 0.5
The same case as in example 0, but now you are allowed to make only one cut. The best thing to do is to cut the piece with weight 3 into two pieces with weights 1.5.
{7, 11, 13}
10
Returns: 0.3999999999999999
{13, 69, 41, 37, 80}
27
Returns: 1.4666666666666668
{1,1000000000,1000000000}
1
Returns: 9.99999999E8
max answer
{50001,50002}
100000
Returns: 3.9999181744576617E-10
small non-zero answer
Submissions are judged against all 121 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CakesEqualization with a public method double fairDivision(vector<int> weights, int maxCuts) · 121 test cases · 2 s / 256 MB per case