彗星撞擊 (APCS 2025-10 中級)
1.0s 256M你正在研究一個恐龍棲息地。棲息地是一個有 \(R\) 列、\(C\) 行的矩形 網格,列座標為 \(0\) 到 \(R-1\),行座標為 \(0\) 到 \(C-1\)。最初每一格的 地面高度都是 \(D\)。
地圖上最初有 \(K\) 隻清醒的恐龍。每隻恐龍都有一個所在座標,而且 同一個座標可能有多隻恐龍。
接著會發生 \(M\) 次彗星撞擊。一次撞擊由中心 \((a,b)\)、奇數邊長 \(S\) 以及深度 \(d\) 描述。令 \(h=\lfloor S/2\rfloor\),撞擊的原始正方形範圍為
\[a-h\le r\le a+h,\qquad b-h\le c\le b+h.\]真正受影響的格子,是這個正方形與地圖範圍的交集。超出地圖的部分直接 忽略。
每次撞擊依照撞擊當下的狀態,套用以下其中一條規則:
- 如果影響範圍內至少有一隻仍清醒的恐龍:
- 範圍內所有清醒恐龍都會變為暈眩。
- 本次撞擊不會改變任何地面高度。
- 如果影響範圍內沒有清醒的恐龍:
- 範圍內每一格的地面高度都減少 \(d\)。
恐龍暈眩後不會再恢復清醒,因此之後的撞擊不應再把牠視為清醒恐龍。 地面可以被重複撞擊,高度也可能變成負數。
請輸出所有撞擊結束後的最高地面高度、最低地面高度,以及仍清醒的 恐龍隻數。
輸入格式
第一行有三個整數 \(R\)、\(C\)、\(D\),代表地圖的列數、行數與初始高度。
第二行有一個整數 \(K\),代表初始清醒恐龍數。
接下來 \(K\) 行,每行有兩個整數 \(r_i\)、\(c_i\),代表一隻恐龍的初始 座標。座標可以重複。
接下來一行有一個整數 \(M\),代表撞擊次數。
接下來 \(M\) 行,每行有四個整數 \(a_j\)、\(b_j\)、\(S_j\)、\(d_j\),依序 代表第 \(j\) 次撞擊的中心、正方形邊長與深度。
限制
- \(1\le R,C,D\le100\)
- \(0\le K\le100\)
- \(0\le r_i<R\)
- \(0\le c_i<C\)
- \(1\le M\le100\)
- \(0\le a_j<R\)
- \(0\le b_j<C\)
- \(1\le S_j\le19\),且 \(S_j\) 為奇數
- \(1\le d_j\le10\)
輸出格式
輸出一行三個以空格分隔的整數:
最高地面高度 最低地面高度 清醒恐龍隻數
評分說明
| 子題組 | 分數 | 額外限制 |
|---|---|---|
| 1 | 60 | \(R=1\) |
| 2 | 40 | 無額外限制 |
範例輸入
1 10 5
5
0 5
0 4
0 4
0 1
0 1
2
0 0 1 4
0 3 3 1
範例輸出
5 1 3
範例解釋
地圖只有第 0 列,共有 10 格,初始高度皆為 5。五隻恐龍中,兩隻在 \((0,1)\)、兩隻在 \((0,4)\)、一隻在 \((0,5)\)。
第 1 次撞擊的中心是 \((0,0)\),邊長為 1,因此只影響 \((0,0)\)。這一格 沒有清醒恐龍,所以高度從 5 減少 4,變成 1。
此時各格高度為:
1 5 5 5 5 5 5 5 5 5
第 2 次撞擊的中心是 \((0,3)\),邊長為 3。原正方形的列範圍是 \([-1,1]\)、行範圍是 \([2,4]\);和地圖取交集後,影響 \((0,2)\)、\((0,3)\)、\((0,4)\)。
\((0,4)\) 有兩隻清醒恐龍,因此這兩隻恐龍都變為暈眩,而且本次所有地面 高度都不變。最後仍清醒的是 \((0,1)\) 的兩隻與 \((0,5)\) 的一隻,共 3 隻。
最高高度是 5,最低高度是 1,所以輸出 5 1 3。
題目來源
APCS 2025 年 10 月中級實作題第 1 題。
題敘參考 ZeroJudge r488「彗星撞擊」 整理,細節可能與正式試題有出入。