Cross-Shaped Tests |
There is an n*n matrix. Each number can be increased or decreased. If we increase a number by x (which may be non-integer), the cost is c*x. If we decrease a number by x, the cost is d*x, where c and d are two non-negative integers.
The theoretical goal is to make every number equal to F, but in practice we only do Q tests, each test is to specify a square, then adding all the numbers in the same row or column, if the difference between the sum and (2n - 1)F is at most e, the test is successful.
Your task is to survive all the tests with minimal cost. It's not hard to see that the actual new matrix might be very different from the theoretical goal.
2 5 12 23 2 1 2 0 0 1 0 0 1 2 3 1 1 3 1 5 3 3 0 0 1 0 0 0 0 1 0 0 2 3 3 3 2 0 1 0 0 3 1 -1 -1 -2 1 1 2 1 2 2
58.00000 0.50000