← 返回题目列表

AtCoder · agc061_d

D. 几乎乘法口诀表

中文机器翻译题面 查看原题

分数: 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