시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 5 | 4 | 4 | 100.000% |
Two m×n matrices A and B are given. Matrix B is obtained from matrix A by row-addition operations and column-subtraction operations. A row-addition operation adds 1 to each entry of a row. A column-subtraction operation subtracts 1 from each entry of a column.
In this task, you have to find the numbers of row-addition operations r1, · · ·, rm to be applied to row 1, · · ·, row m of A respectively such that the following properties hold.
You should concatenate the values r1, · · ·, rm and output it as a single m-digit integer r1 · · · rm (with possibly leading zeros). If the given matrix B cannot be obtained from the given matrix A with 0 to 9 row-addition operations on each row and 0 to 9 column-subtraction operations on each column, your program should output the value −1.
The first line contains two integers m and n separated by a space, 1 ≤ m ≤ 100, 1 ≤ n ≤ 100. The matrix A is given by the next m lines for row 1 to row m. Each of these m lines contains n integers, with a space between two adjacent integers. Similarly, the matrix B is given by the next m lines. Each entry of the matrices is an integer between −1000 and 1000 inclusively.
The output file contains an m-digit integer.
2 3 1 2 3 4 5 6 1 0 0 0 -1 -1
40
Let
\[A = \begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}, B = \begin{bmatrix}1&0&0\\0&-1&-1\end{bmatrix}\text{.}\]
The required row-additions and column-subtractions are shown as:
\[ \begin{array}{c|ccc} &-4&-6&-7 \\ \hline +4 & 1 & 2 & 3 \\ +0 & 4 & 5 & 6 \end{array} \]
Since there are 4 and 0 row-additions operations for row 1 and row 2 respectively, the required output is
\[40\]
after checking that 4 is the smallest possible number of row operations for row 1.
3 3 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9
420
Let
\[A = \begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}, B = \begin{bmatrix}1&4&7\\2&5&8\\3&6&9\end{bmatrix}\text{.}\]
The required row-additions and column-subtractions are shown as:
\[ \begin{array}{c|ccc} &-4&-2&-0 \\ \hline +4 & 1 & 2 & 3 \\ +2 & 4 & 5 & 6 \\ +0 & 7 & 8 & 9 \end{array} \]
Since there are 4, 2, and 0 row-additions operations for row 1, row 2, and row 3, the required output is
\[420\]
after checking that 4 is the smallest possible number of row operations for row 1.
2 1 0 -9 9 9
-1
Let
\[A = \begin{bmatrix}0\\-9\end{bmatrix}, B = \begin{bmatrix}9\\9\end{bmatrix}\text{.}\]
It can be checked that it is impossible to obtain B from A with 0 to 9 row-additions on each row and 0 to 9 column-subtractions on each column. So the output should be −1.