彗星撞擊 (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.\]

真正受影響的格子,是這個正方形與地圖範圍的交集。超出地圖的部分直接 忽略。

每次撞擊依照撞擊當下的狀態,套用以下其中一條規則:

  1. 如果影響範圍內至少有一隻仍清醒的恐龍:
    • 範圍內所有清醒恐龍都會變為暈眩。
    • 本次撞擊不會改變任何地面高度。
  2. 如果影響範圍內沒有清醒的恐龍:
    • 範圍內每一格的地面高度都減少 \(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「彗星撞擊」 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。