回『IOI/APCS』
h027. 202001_2 矩陣總和
標籤 : APCS
通過比率 : 1092人/1173人 ( 93% ) [非即時]
評分方式：
Tolerant

最近更新 : 2022-02-15 23:15

內容

矩陣是將一群元素整齊的排列成一個矩形，在矩陣中的橫排稱為列 (row)，直排稱為行 (column)，一個n×m的矩陣有 n 列 m 行，其中以 Xij 來表示矩陣 X 中的第 i 列第 j 行的元素。在同樣大小的矩陣中，我們定義兩個矩陣的距離為兩矩陣中對應位置相同但值不相同的元素數量。

有一個 s×t 的小矩陣 A，和一個 n×m 的大矩陣 B，請計算 B 矩陣的子矩陣中，與 A 矩陣距離不超過 r 的子矩陣個數，並從這些距離 A 不超過 r 的子矩陣中，找到總和與 A 差異最小的值。

以範例二為例，B 矩陣中有3個子矩陣與 A 距離不超過 2，其中 A 的元素總和為 1+2+1+2+4+2+2+4+5=23，B1 的元素總和為20，B2 的元素總和為 24 ，B3 的元素總和為 28。與 A 元素總和最小值的為 |23−24|=1。

 

輸入說明

第一行有五個正整數s，t，n，m 與 r。

接下來 s 行(line)每行包含 t 個數，第 i 行第 j 個數代表 Aij 的值。

接下來 n 行(line)每行包含 m 個數，第 i 行第 j 個數代表 Bij 的值。

同一行間數字以空格隔開。

測資範圍如下：

  • 1≤s≤n≤10
  • 1≤t≤m≤100
  • 1≤r≤100
  • 0≤Aij,Bij≤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
提示 ：
標籤:
APCS
出處:
2020年1月APCS [管理者： ktlai@cmgsh. ... (賴楷宗) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
41702 a0916933001@ ... (小律) h027
測資超範圍
221 2024-08-18 18:17
40799 glps1004@gma ... (Ian) h027
C++解
332 2024-06-13 19:56
37639 zhoudaniel02 ... (周孝倫) h027
土法煉鋼就行了
658 2023-09-22 23:11
35240 willy633526@ ... (ByTech) h027
python 題解
721 2023-05-18 11:20
34922 luray0601@gm ... (QWERTYPIG) h027
C++題解(含想法)
736 2023-04-27 08:35