h027.
202001_2 矩陣總和
內容
矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (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}$ 的值。
同一行間數字以空格隔開。
測資範圍如下：
- $1 \leq s \leq n \leq 10$
- $1 \leq t \leq m \leq 100$
- $1 \leq r \leq 100$
- $0 \leq A_{ij},B_{ij}≤9$
本題包含三個子題組，每個子題組配分如下：
- 第 1 子題組共 50 分： $s = n = 1$
- 第 2 子題組共 50 分： 無額外限制。
輸出說明
輸出有兩行：
第一行輸出符合條件的子矩陣個數。
第二行輸出所有符合條件的子矩陣中，數字總和與$A$相差最小的值，若找不到符合條件的子矩陣，則輸出$-1$。
範例輸入
#1
1 3 1 10 1 7 4 7 6 7 7 7 4 5 0 4 4 7
範例輸出
#1
3 2
範例輸入
#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
範例輸出
#2
3 1
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
提示 ：
標籤:
出處:
2020年1月APCS
[管理者：
ktlai@cmgsh.
...
(賴楷宗)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 37639 |
|
h027 | 285 | 2023-09-22 23:11 | |
| 35240 |
|
h027 | 388 | 2023-05-18 11:20 | |
| 34922 |
|
h027 | 432 | 2023-04-27 08:35 | |
| 29274 | alan8656 (阿伯) | h027 | 863 | 2022-02-10 22:12 |