分数: 1000 点
问题陈述
有正整数 N, M,以及 N \times M 正整数矩阵 A_{i, j}。两人份 (严格)增加 正整数序列 X = (X_1, \ldots, X_N) 和 Y = (Y_1, \ldots, Y_M),我们定义惩罚 D(X, Y) as \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}|.
找到两个 (严格)增加 正整数序列 X 和 Y 这样 D(X, Y) 是尽可能小的。
约束
- 1 \leq N, M \leq 5
- 1 \leq A_{i, j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
A_{1,1} \ldots A_{1,M}
\vdots
A_{N,1} \ldots A_{N,M}
输出
按以下格式输出您的答案:
D_{min}
X_1 \ldots X_N
Y_1 \ldots Y_M
在这里, D_{min} 是可能的最小惩罚,并且应满足以下条件:
- D(X, Y) 应等于 D_{min}.
- X_i < X_{i + 1} (1 \leq i \leq N - 1).
- Y_j < Y_{j + 1} (1 \leq j \leq M - 1).
- 1 \leq X_i \leq 2\cdot 10^9 (1 \leq i \leq N).
- 1 \leq Y_j \leq 2\cdot 10^9 (1 \leq j \leq M).
可以证明存在满足最后两个条件的最优解。
示例输入 1
1 1 853922530
示例输出 1
0 31415 27182
示例输入 2
3 3 4 4 4 4 4 4 4 4 4
示例输出 2
5 1 2 3 1 2 3
示例输入 3
3 4 4674 7356 86312 100327 8737 11831 145034 167690 47432 66105 809393 936462
示例输出 3
357 129 216 1208 39 55 670 775