Marbles and Boxes
Time limit: 0.5 s.
Memory limit: 256 MB
There are 3 boxes containing marbles of 3 different colors. For each box, you know how many marbles of each color it contains.
Your goal is to move the minimum number of marbles from one box to another so that, after all the moves:
- no two marbles in the same box are of different colors, and
- no two marbles in different boxes are of the same color.

Input
The initial distribution of marbles into boxes is given by a \(3 \times 3\) matrix \(A\), where \(A_{i, j}\) represents the number of marbles of color \(i\) in box \(j\) \((0 \le A_{i,j} \le 100)\).
The input consists of three lines: \(A_{1, 1} \ A_{1, 2} \ A_{1, 3}\\ A_{2, 1} \ A_{2, 2} \ A_{2, 3}\\ A_{3, 1} \ A_{3, 2} \ A_{3, 3}\)
Output
Print a single integer - the minimum number of marbles that need to be moved.
Scoring
In this problem, each test case will be scored separately. Your score is the sum of the scores for all test cases.
- In 30% of the test cases, box 3 is empty.
- In another 30% of test cases, boxes 2 and 3 are both empty.
Examples
Input
2 0 0
3 0 0
0 0 0
Output
2
Input
3 1 0
9 5 0
0 0 0
Output
8
Input
3 1 7
6 6 8
2 4 5
Output
25
Note
Explanation for the first example: In the first box there are 2 marbles of the first color and 3 marbles of the second color. The other two boxes are empty. If we move 2 marbles of the first color to the second box, we achieved our goal. It can not be done in fewer moves, so the answer is 2.
Explanation for the second example: The optimal solution is to move 3 marbles of the first color from the first box into the second box, and 5 marbles of the second color from the second box into the first box.
The third example is shown in the picture.
Solution
In the final arrangement, each colour must occupy a different box. There are only \(3!=6\) assignments of colours to boxes.
For each assignment, the marbles already in their assigned boxes do not move; every other marble must move. Maximize the number kept in place, then subtract it from the total number of marbles.
The complexity is \(O(1)\).
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int a[3][3];
int total = 0;
for (int colour = 0; colour < 3; colour++) {
for (int box = 0; box < 3; box++) {
cin >> a[colour][box];
total += a[colour][box];
}
}
int boxes[3] = {0, 1, 2};
int mostKept = 0;
do {
int kept = 0;
for (int colour = 0; colour < 3; colour++) {
kept += a[colour][boxes[colour]];
}
mostKept = max(mostKept, kept);
} while (next_permutation(boxes, boxes + 3));
cout << total - mostKept << '\n';
}