a491: 貨物集中問題
Tags :
Accepted rate : 50人/70人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-21 16:29

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

第一列有一個整數 N,代表測試資料有幾組。

第二列有兩個數字 R, C, (1 <= R, C <= 2000)分別代表第一組測試資料的二維矩陣列數與行數。接下來的 R 列,每一列有 C 個整數,這 R 列中的第 i 列的第 j 個整數代表 (i, j) 區的儲存貨物量,且均 <=100000。每兩個整數之間都會有一個空白隔開。

Output

第一列請輸出每一組測試資料貨物應該集中於那一分區 (i, j),方能使其整體移動成本最小,以兩個整數表示,整數間以一個空白區隔。如有多個分區滿足條件,請輸出字典順序最小者。

第二列請輸出其所需要的最小成本。

Sample Input
1
3 4
4 2 0 1
0 1 1 0
1 0 0 3
Sample Output
1 2
2400
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1M
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <10M
不公開 測資點#4 (20%): 1.0s , <10M
不公開 測資點#5 (20%): 1.0s , <50M
Hint :

請注意:

1. 原題測資 R, C <=100,與本題要求不盡相同。

2. ZJ 似乎會把換行吃掉,因此輸入格式並非如上所述。

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」