#P13096. [AGC061D] Almost Multiplication Table

    ID: 12280 传统题 3000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200二分构造数学枚举搜索数据结构回溯法

[AGC061D] Almost Multiplication Table

题目描述

给定正整数 N, MN,\ M 和一个 N×MN \times M 的正整数矩阵 Ai,jA_{i,j}。对于两个严格单调递增的正整数序列 X=(X1,…,XN), Y=(Y1,…,YM)X = (X_1, \ldots, X_N),\ Y = (Y_1, \ldots, Y_M),定义惩罚值 D(X,Y)D(X, Y) 为 $\max_{1 \leq i \leq N,\ 1 \leq j \leq M} |X_i Y_j - A_{i,j}|$。

请你求出能够最小化 D(X,Y)D(X, Y) 的两个严格单调递增正整数序列 X, YX,\ Y。

输入格式

输入从标准输入读入,格式如下:

NN MM
A1,1A_{1,1} A1,2A_{1,2} …\ldots A1,MA_{1,M}
⋮\vdots
AN,1A_{N,1} AN,2A_{N,2} …\ldots AN,MA_{N,M}

输出格式

请按如下格式输出答案:

DminD_{min} X1X_1 …\ldots XNX_N Y1Y_1 …\ldots YMY_M

其中 DminD_{min} 是最小的惩罚值,并且需满足以下条件:

  • D(X,Y)=DminD(X, Y) = D_{min}。
  • Xi<Xi+1X_i < X_{i+1}(1≤i≤N−11 \leq i \leq N-1)。
  • Yj<Yj+1Y_j < Y_{j+1}(1≤j≤M−11 \leq j \leq M-1)。
  • 1≤Xi≤2⋅1091 \leq X_i \leq 2 \cdot 10^9(1≤i≤N1 \leq i \leq N)。
  • 1≤Yj≤2⋅1091 \leq Y_j \leq 2 \cdot 10^9(1≤j≤M1 \leq j \leq M)。

可以证明,满足最后两个条件的最优解一定存在。

输入输出样例 #1

输入 #1

1 1
853922530

输出 #1

0
31415
27182

输入输出样例 #2

输入 #2

3 3
4 4 4
4 4 4
4 4 4

输出 #2

5
1 2 3 
1 2 3

输入输出样例 #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

说明/提示

限制条件

  • 1≤N,M≤51 \leq N, M \leq 5
  • 1≤Ai,j≤1091 \leq A_{i,j} \leq 10^9(1≤i≤N1 \leq i \leq N,1≤j≤M1 \leq j \leq M)
  • 输入中的所有数值均为整数。