c018. 202010_2. 人口遷移

Content

$R \times C$ 的平面上有一些城市，每天每個城市會向每個它相鄰的城市遷移 $\cfrac{\text{人數}}{k}$ 個人（整數除法，無條件捨去），請模擬出 $m$ 天之後的結果，輸出人數最少及最多的城市人數。

城市人數若為 $-1$ 則代表該位置並非城市，不能由任何城市遷移至此。

下圖是第一筆範例測資模擬的結果

Input

輸入的第一行包含四個正整數 $R, C, k, m, (1\leq R, C, m \leq 50, 4\leq k \leq 50)$

接下來包含 $R$ 行，每行包含 $C$ 個整數，對於第 $i$ 行的第 $j$ 個整數 $a_{i, j}\ (-1 \leq a_{i,j} \leq 100)$，如果是 -1 表示這個座標沒有城市，否則表示這個座標的城市人數數量，保證是非負整數。

配分

20%: $R=1, m=1$
30%: $R=1$
50%: 無其他限制

Output

第一行，輸出在 m 天之後，人數最少的城市的人數。

第二行，輸出在 m 天之後，人數最多的城市的人數。

Sample Input #1

2 3 4 1
10 2 -1 
5 -1 2

Sample Output #1

2
7

Sample Input #2

4 5 5 3
18 30 -1 27 16
-1 10 -1 38 18
8 16 18 33 30
23 21 32 -1 15

Sample Output #2

15
28

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M

Hint ：

範例測資二每天的狀況如下
D1:
21 23 -1 27 18
-1 15 -1 31 25
13 14 24 31 24
20 22 27 -1 18

D2:
21 22 -1 26 22
-1 15 -1 29 23
15 19 25 27 26
18 21 25 -1 19

D3:
21 21 -1 25 23
-1 16 -1 28 25
15 22 23 27 23
19 20 24 -1 21

Tags:

出處:

2020年10月APCS 演算法海牛 [管理者：

ktlai (K．我已霸榜．Tlai)

]

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