c482: pF 絕對多數
標籤 :
通過比率 : 100% (11 人 / 11 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-02-22 22:59

內容

在一群 M 個數字中,如果有某個數字出現的次數超過 M/2,則稱為此數為這群數的「絕對多數」,

一群數字最多有一個絕對多數,但也可能沒有,例如(1,2,1,1,3)的絕對多數是 1,

而(1,2,1,3)沒有絕對多數,本題的任務是計算絕對多數。


每一筆測試資料包含一個 N×N 的整數方陣 A 與 q 個計算要求,矩陣的元素儲存在A[0][0]~A[N-1][N-1],

矩陣的橫的一排稱為列(row),直的一排稱為行(column)。

每一個計算要求包含四個整數 r1、r2、c1、c2,0 <= r1 <= r2 < N,0 <= c1 <= c2 < N,

代表一個子矩陣 A[r1:r2][c1:c2],也就是第 r1列到第 r2列且第 c1行到第 c2行所組成的子矩陣,

我們要計算這個子矩陣中是否有絕對多數。

下圖為一個 N=5 的方陣 A,子矩陣 A[0:1][0:2]共有六個元素,出現最多的元素是 1,出現了 3 次,並未超過總數的一半,因此沒有絕對多數。

而子矩陣 A[2:4][1:3]共有 9 個元素,3 出現了 5 次,超過總數的一半,因此絕對多數是 3。

對於某些子題,你的程式必須很有效率的決定是否存在絕對多數。

輸入說明

輸入包含多個測試資料,每筆測試資料包含一個輸入矩陣以及若干個子矩陣計算要求。

每個測試資料的第一行(line)是矩陣大小的 N,接下來 N 行(lines)是矩陣內容,以row-major 方式排列,

由第 0 列(row)至第 N-1 列,每列有 N 個非負整數是該列第 0 行(column)至第 N-1 行(column),數字之間以一個空白間格。

接著一行包含一個整數 q 代表計算要求數,其下有 q 行,每行是一個計算要求依序是子矩陣範圍的四個整數r1,r2,c1,c2。

一筆測試資料結束後是下一筆測試資料,若 N=0 代表輸入資料結束。

輸出說明

針對每個測試資料的每個計算要求,以一行輸出絕對多數,如果沒有絕對多數則輸出-1。

範例輸入
5
1 2 3 3 2
2 1 1 2 3
1 2 3 1 1
0 2 3 3 1
0 3 1 3 2
2
0 1 0 2
2 4 1 3
0

範例輸出
-1
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (33%): 3.0s , <1M
公開 測資點#1 (33%): 3.0s , <50M
公開 測資點#2 (34%): 3.0s , <50M
提示 :

本題共有四組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

每組測試資料的輸入檔參數 N、D、Q 和 S 如下,其中 N 是矩陣大小的上限,D 代表陣列中數字
的上限,Q 是計算需求總數即該檔案中 q 值的總和,也就是該子題總共輸出 Q 行,S 則
是輸入檔案中,所有矩陣的元素總量,即 N2的總和。


第一組 15 分, N <= 100  、D <= 5000    、Q <= 40、S <= 32000。
第二組 27 分, N <= 1010、D <= 5000    、Q <= 30、S <= 3200000。
第三組 19 分, N <= 1010、D <= 2^31-1、Q <= 50、S <= 3200000。
第四組 39 分, N <= 2000、D <= 2^31-1、Q <= 70、S <= 12500000。

 

測資看起來是 rand() !

第四筆因為檔案太大無法上傳~~

標籤:
出處:
104學年度全國資訊學科能力競賽 [編輯:
andy89923 (CTFang)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」