矩陣是將一群元素整齊的排列成一個矩形,在矩陣中的橫排稱為列 (row),直排稱為行 (column),一個$n \times m$的矩陣有 $n$ 列 $m$ 行,其中以 $X_{ij}$ 來表示矩陣 $X$ 中的第 $i$ 列第 $j$ 行的元素。在同樣大小的矩陣中,我們定義兩個矩陣的距離為兩矩陣中對應位置相同但值不相同的元素數量。
有一個 $s \times t$ 的小矩陣 $A$,和一個 $n \times m$ 的大矩陣 $B$,請計算 $B$ 矩陣的子矩陣中,與 $A$ 矩陣距離不超過 $r$ 的子矩陣個數,並從這些距離 $A$ 不超過 $r$ 的子矩陣中,找到總和與 $A$ 差異最小的值。
以範例二為例,$B$ 矩陣中有3個子矩陣與 $A$ 距離不超過 $2$,其中 $A$ 的元素總和為 $1+2+1+2+4+2+2+4+5=23$,$B_1$ 的元素總和為$20$,$B_2$ 的元素總和為 $24$ ,$B_3$ 的元素總和為 $28$。與 $A$ 元素總和最小值的為 $|23-24| = 1$。
第一行有五個正整數$s$,$t$,$n$,$m$ 與 $r$。
接下來 $s$ 行(line)每行包含 $t$ 個數,第 $i$ 行第 $j$ 個數代表 $A_{ij}$ 的值。
接下來 $n$ 行(line)每行包含 $m$ 個數,第 $i$ 行第 $j$ 個數代表 $B_{ij}$ 的值。
同一行間數字以空格隔開。
測資範圍如下:
本題包含三個子題組,每個子題組配分如下:
輸出有兩行:
第一行輸出符合條件的子矩陣個數。
第二行輸出所有符合條件的子矩陣中,數字總和與$A$相差最小的值,若找不到符合條件的子矩陣,則輸出$-1$。
1 3 1 10 1 7 4 7 6 7 7 7 4 5 0 4 4 7
3 2
3 3 5 5 2 1 2 1 2 4 2 2 4 5 1 2 1 2 3 2 4 2 4 2 2 4 2 3 5 3 2 4 2 0 3 2 4 5 5
3 1
ID | User | Problem | Subject | Hit | Post Date |
41702 | a0916933001@ ... (小律) | h027 | 114 | 2024-08-18 18:17 | |
40799 | glps1004@gma ... (Ian) | h027 | 189 | 2024-06-13 19:56 | |
37639 | zhoudaniel02 ... (周孝倫) | h027 | 552 | 2023-09-22 23:11 | |
35240 | willy633526@ ... (ByTech) | h027 | 631 | 2023-05-18 11:20 | |
34922 | luray0601@gm ... (QWERTYPIG) | h027 | 626 | 2023-04-27 08:35 |