a491. 貨物集中問題 - 高中生程式解題系統

內容

一個矩形平面大型倉儲空間，共有 $R \times C$ 個分區，其中 $R$ 代表矩形的列數， $C$ 代表矩形的行數。此倉儲空間以一 $R \times C$ 二維矩陣表示，倉儲空間中的每一分區以二維座標表示，二維矩陣中每一分區的內容代表各分區的儲存貨物量。今因整個倉儲空間保養維修的因素，需將所有分區的貨物暫時集中於某一分區內，並假設任一分區的容量均可以容納目前倉儲空間中的總貨物容量。因為貨物移動需要移動成本，假定一個單位的貨物從現在的分區移動到相鄰上下左右任意一個分區的成本為 $100$ 元，請寫一程式決定貨物應該集中於哪一分區，其整體移動成本為最小。

輸入說明

$N$

$R_{1}$ $C_{1}$

$A_{1, 1, 1}$ $A_{1, 1, 2}$ $\dots$ $A_{1, 1, C_{1}}$

$A_{1, 2, 1}$ $A_{1, 2, 2}$ $\dots$ $A_{1, 2, C_{1}}$

$⋮$

$A_{1, R_{1}, 1}$ $A_{1, R_{1}, 2}$ $\dots$ $A_{1, R_{1}, C_{1}}$

$R_{2}$ $C_{2}$

$A_{2, 1, 1}$ $A_{2, 1, 2}$ $\dots$ $A_{2, 1, C_{2}}$

$A_{2, 2, 1}$ $A_{2, 2, 2}$ $\dots$ $A_{2, 2, C_{2}}$

$⋮$

$A_{2, R_{2}, 1}$ $A_{2, R_{2}, 2}$ $\dots$ $A_{2, R_{2}, C_{2}}$

$⋮$

$R_{N}$ $C_{N}$

$A_{N, 1, 1}$ $A_{N, 1, 2}$ $\dots$ $A_{N, 1, C_{N}}$

$A_{N, 2, 1}$ $A_{N, 2, 2}$ $\dots$ $A_{N, 2, C_{N}}$

$⋮$

$A_{N, R_{N}, 1}$ $A_{N, R_{N}, 2}$ $\dots$ $A_{N, R_{N}, C_{N}}$

$N$ 代表測試資料的筆數。
$R_{i}, C_{i}$ 代表第 $i$ 筆測試資料的矩陣大小為 $R_{i} \times C_{i}$ 。
$A_{i, j, k}$ 代表第 $i$ 筆測試資料的矩陣 $(j, k)$ 位置的值。
$1 \leq N \leq 10$ 。
對於所有的 $i \in {1, 2, \dots, N}$ ，均有 $1 \leq R_{i}, C_{i} \leq 2000$ 。
對於所有的 $i \in {1, 2, \dots, N}, j \in {1, 2, \dots, R_{i}}, k \in {1, 2, \dots, C_{i}}$ ，均有 $0 \leq A_{i, j, k} \leq 10^{5}$ 。
輸入的數皆為整數。

輸出說明

$i_{1}^{*}$ $j_{1}^{*}$

$P_{1}$

$i_{2}^{*}$ $j_{2}^{*}$

$P_{2}$

$⋮$

$i_{N}^{*}$ $j_{N}^{*}$

$P_{N}$

$i_{k}^{*}, j_{k}^{*}$ 為兩整數，代表第 $k$ 筆測試資料中的貨物應集中於 $(i_{k}^{*}, j_{k}^{*})$ 分區。如有多個符合條件的 $(i_{k}^{*}, j_{k}^{*})$ ，請輸出字典順序最小的那組。
$P_{k}$ 為一整數，代表第 $k$ 筆測試資料所需的最小成本。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (16%): 2.0s , <1M
不公開測資點#1 (16%): 2.0s , <1M
不公開測資點#2 (17%): 2.0s , <1M
不公開測資點#3 (17%): 2.0s , <10M
不公開測資點#4 (17%): 2.0s , <10M
不公開測資點#5 (17%): 2.0s , <50M

提示：

範例測試中的第一筆測試資料，只要設 $(i_{1}^{*}, j_{1}^{*})$ 為 $(1, 2)$ ，即可得到最小成本 $2400$ 。

範例測試中的第二筆測試資料，能得到最小成本 $400$ 的 $(i_{2}^{*}, j_{2}^{*})$ 有 $(2, 2), (2, 3), (3, 2), (3, 3)$ ，故取字典序最小的 $(2, 2)$ 。

標籤:

出處:

100學年度彰雲嘉區資訊學科能力競賽 [管理者： xavier13540 (柊四千) ]

編號	身分	題目	主題	人氣	發表日期
40048	xavier13540 (柊四千)	a491	作者提供的解法	293	2024-04-24 23:58
40047	xavier13540 (柊四千)	a491	作者提供的解法	182	2024-04-24 23:57