/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
正の整数 N, M と N \times M 正整数行列 A_{i, j} があります。二つの（狭義）単調増加正整数列 X = (X_1, \ldots, X_N), Y = (Y_1, \ldots, Y_M) に対し、ペナルティ D(X, Y) を \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}| と定義します。
D(X, Y) を最小化する二つの（狭義）単調増加正整数列 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
Score : 1000 points
Problem Statement
There are positive integers N, M, and an N \times M positive integer matrix A_{i, j}. For two (strictly) increasing positive integer sequences X = (X_1, \ldots, X_N) and Y = (Y_1, \ldots, Y_M), we define the penalty D(X, Y) as \max_{1 \leq i \leq N, 1 \leq j \leq M} |X_i Y_j - A_{i, j}|.
Find two (strictly) increasing positive integer sequences X and Y such that D(X, Y) is the smallest possible.
Constraints
- 1 \leq N, M \leq 5
- 1 \leq A_{i, j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N M
A_{1,1} \ldots A_{1,M}
\vdots
A_{N,1} \ldots A_{N,M}
Output
Output your answer in the following format:
D_{min}
X_1 \ldots X_N
Y_1 \ldots Y_M
Here, D_{min} is the smallest possible penalty and the following conditions should be satisfied:
- D(X, Y) should be equal to 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).
One can show that there is an optimal solution satisfying the last two conditions.
Sample Input 1
1 1 853922530
Sample Output 1
0 31415 27182
Sample Input 2
3 3 4 4 4 4 4 4 4 4 4
Sample Output 2
5 1 2 3 1 2 3
Sample Input 3
3 4 4674 7356 86312 100327 8737 11831 145034 167690 47432 66105 809393 936462
Sample Output 3
357 129 216 1208 39 55 670 775