580 . 人口遷移
TopCoder
Tags
Description
$R×C$ 的平面上有一些城市，每天每個城市會向每個它相鄰的城市遷移 $\frac{\text{人數}}{k}$ 個人（整數除法，無條件捨去），請模擬出 $m$ 天之後的結果，輸出人數最少及最多的城市人數。
城市人數若為 $−1$ 則代表該位置並非城市，不能由任何城市遷移至此。
下圖是第一筆範例測資模擬的結果。
Input Format
輸入的第一行包含四個正整數 $R,C,k,m,(1\le R,C,m\le50,4\le k\le50)$。
接下來包含 $R$ 行，每行包含 $C$ 個整數，對於第 $i$ 行的第 $j$ 個整數 $a_{i,j}(−1\le a_{i,j}\le100)$，如果是 $-1$ 表示這個座標沒有城市，否則表示這個座標的城市人數數量，保證是非負整數。
Output Format
第一行，輸出一個整數，代表在 $m$ 天之後，人數最少的城市的人數。
第二行，輸出一個整數，代表在 $m$ 天之後，人數最多的城市的人數。
Sample Input 1
2 3 4 1
10 2 -1
5 -1 2
10 2 -1
5 -1 2
Sample Output 1
2
7
7
Sample Input 2
1 4 5 3
5 -1 6 8
5 -1 6 8
Sample Output 2
5
8
8
Hints
Problem Source
APCS 考古
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~5 | $R=1,M=1$ | 20 |
| 3 | 6~9 | R=1 | 30 |
| 4 | 0~15 | 無額外限制 | 50 |