回分類題庫
h137: G.華麗內餡格狀超好吃巧克力
關鍵字: NPSC 2014 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 19 Times / 15 Users | Submit : 158 Times / 22 Users | Accepted rate : 68%
題目加入時間 : 2015-11-10 13:33

Content: 简体中文

小小郭不喜歡吃巧克力,但是因為他實在太夯了,每年情人節都會收到巨量巧克力,這讓他非常困擾。他只好想辦法把收到的巧克力分送給親朋好友們。

現在小小郭想要分送一片大小為 n × m 的華麗內餡格狀超好吃巧克力,而小小郭的好朋友胖胖天獲得先行選擇的權利。因為巧克力實在太多了,小小郭希望胖胖天可以從裡面拿走至少兩格巧克力,而且拿走的部分必需是一個長方形。每格巧克力因為內餡不同,會各自有一個好吃度。現在胖胖天想要使得他選擇的部分平均好吃度最大,請你幫幫他。 

Input:

輸入的第一行有一個正整數 T,代表測試資料的筆數。

每一筆測試資料開始有一行兩個整數 n, m,代表華麗內餡格狀超好吃巧克力的大小。接下來 n 行,每行有 m 個整數 ai,j 代表每格的好吃度。 

Output:

對於每一筆測試資料請輸出一行,包含一個分數 p/q 表示最大的平均好吃度,其中 p, q 皆為正整數且 gcd(p, q) = 1。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 3
8 1 6
3 5 7
4 9 2
4 4
1 15 14 4
12 6 7 9
8 10 11 5
13 3 2 16

Sample Output :

7/1
29/2

Hint :

範例說明:

第一筆測試資料中最好的是由好吃度 5, 9 的格子組成的長方形

第二筆測試資料中最好的是由好吃度 15, 14 的格子組成的長方形 

Author :

NPSC 2014 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum