BYU15W_2 - Grid Arithmetic
Your task is to take an N-by-N matrix and pick numbers that can be added or subtracted from one another to most closely approximate 0. The catch is that you must only use exactly one number in each row and column—no more, no less.
Example
Consider the following matrix where N = 3.
1 75 10 22 500 3 9 125 50
75 - 22 - 50 = 3 is the correct answer. 10 - 1 - 9 = 0, but 1 and 9 are from the same column. 3 - 1 = 2, but does not use enough numbers.
Input
The first line contains a single positive integer T, representing the number of test cases. T test cases follow. Each test case begins with a line containing a single integer N, representing the size of the matrix. The next N lines each contain N space-separated integers, representing the matrix.
Output
For each test case, output a single line containing the absolute value of the total found that is closest to 0.
Sample
Input 2 2 1 5 4 3 3 1 75 10 22 500 3 9 125 50 Output 1 3
hide comments
lord_poseidon:
2017-10-01 09:35:24
AC in one go, backtracking, assume n <= 10 |
|
martin richardt:
2015-11-05 12:06:37
nevermind. Last edit: 2015-11-05 14:10:54 |
|
:D:
2015-04-08 22:35:30
I assert checked that N <= 10, as Rupesh has posted. You can also assume all sums will fit into 32b signed integer. |
|
Fernando Ferreira de Oliveira [USJT]:
2015-03-30 17:13:58
What is the maximum value of N? |
|
[themighty] deathsurgeon:
2015-03-29 22:49:53
My AC solution assumes n<=10 |
|
Mitch Schwartz:
2015-03-29 12:55:37
Please include constraints. |
Added by: | BYU Admin |
Date: | 2015-03-28 |
Time limit: | 1s-4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA |