AT_agc061_d.[AGC061D] Almost Multiplication Table

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定正整数 $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$ 。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\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

说明/提示

限制条件

$1 \leq N, M \leq 5$
$1 \leq A_{i,j} \leq 10^9$ （ $1 \leq i \leq N$ ， $1 \leq j \leq M$ ）
输入中的所有数值均为整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页