50022. Matrix

I'm a slow walker, but I never walk backwards.

Problem Description

Read problems statements in Mandarin ChineseMorris AI 翻譯:
在 $m \times n$ 個盤面上恰好填入 $1$ 到 $mn$ 的所有數字,現在給與每一行、每一列的總和,請逆推回去得到原始盤面。如果盤面不只有一種,輸出任一種皆可,反之,無解盤面請輸出 no solution 一行。

There is a $m$ by $n$ matrix consisting of integers from 1 to $mn$. You are given the sum of the rows and the sums of the columns, and please write a program to determine the number in each cell of the matrix. Consider the following example.

R\C 1 2 3 4 $R\lbrack ]$
1 1 2 3 4 10
2 5 6 7 8 26
3 9 10 11 12 42
$C\lbrack ]$ 15 18 21 24 none

Now you are given $m = 3$, $n = 4$, and $10$, $26$, and $42$ as the sums of rows, and $15$, $18$, $21$ and $24$ as the sums of columns. The locations of all numbers will be as above. Your task is to print the numbers as a $m$ by $n$ matrix. If there are no solutions, print no solution.

Subtasks

  • 10pt. $n = 1$ or $m = 1$.
  • 15pt. $m = n = 2$, and there is exacly one solution.
  • 15pt. $m = n = 2$. and there could be no solution.
  • 50pt. $m \times n \le 12$, and there could be no solution.
  • 10pt. $m \times n \le 16$, and there could be no solution.

Sample Input

1 3
6
1 2 3
2 1
1 2
3
3 2
6 6 9
6 15
4 4
10 26 42 58
28 32 36 40

Sample Output

1 2 3
1
2
1 5
2 4
3 6
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Discussion