BallsSeparating
SRM 568 · 2012-12-13 · by rng_58
Problem Statement
Fox Ciel wants to separate the balls by colors. In each operation, she can pick a single ball from some box and put it into another box. She considers the balls to be separated if no box contains balls of more than one color.
Return the minimal number of operations required to separate the balls. If this is impossible, return -1.
Constraints
- red, green and blue will each contain between 1 and 50 elements, inclusive.
- red, green and blue will contain the same number of elements.
- Each element of red, green and blue will be between 1 and 1,000,000, inclusive.
{1, 1, 1}
{1, 1, 1}
{1, 1, 1}
Returns: 6
One way to separate the balls in six operations is as follows: Move a red ball from box 1 to box 0. Move a red ball from box 2 to box 0. Move a green ball from box 0 to box 1. Move a green ball from box 2 to box 1. Move a blue ball from box 0 to box 2. Move a blue ball from box 1 to box 2. The pictures on the left and on the right show the initial and the final states of the balls, respectively.
{5}
{6}
{8}
Returns: -1
It is impossible to separate the balls.
{4, 6, 5, 7}
{7, 4, 6, 3}
{6, 5, 3, 8}
Returns: 37
{7, 12, 9, 9, 7}
{7, 10, 8, 8, 9}
{8, 9, 5, 6, 13}
Returns: 77
{842398, 491273, 958925, 849859, 771363, 67803, 184892, 391907, 256150, 75799}
{268944, 342402, 894352, 228640, 903885, 908656, 414271, 292588, 852057, 889141}
{662939, 340220, 600081, 390298, 376707, 372199, 435097, 40266, 145590, 505103}
Returns: 7230607
Submissions are judged against all 158 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BallsSeparating with a public method int minOperations(vector<int> red, vector<int> green, vector<int> blue) · 158 test cases · 2 s / 256 MB per case