磁磚拼貼 (APCS 2026-06 初級)

1.0s 256M

師傅乙要為一塊高 \(H\)、寬 \(W\) 的長方形地面鋪設磁磚。磁磚不能旋轉,且必須依原方向密鋪;也就是說,若選擇高 \(h_i\)、寬 \(w_i\) 的磁磚,必須滿足 \(h_i\) 整除 \(H\) 且 \(w_i\) 整除 \(W\),才可以完整鋪滿地面。

客人提供 \(N\) 種磁磚款式方案。選擇第 \(i\) 種款式後:

  • 每片磁磚成本為 \(C_i\) 元。
  • 至少要購買 \(M_i\) 片。
  • 若購買的磁磚數量超過實際需要的數量,多出來的每片可用 \(S_i\) 元轉賣給其他師傅。

保證至少有一種款式可以完整鋪滿地面。請求出師傅完成鋪設的最小成本。

輸入格式

第一行有兩個整數 \(H\) 與 \(W\)。

第二行有一個整數 \(N\)。

接下來 \(N\) 行,第 \(i\) 行有五個整數 \(h_i, w_i, C_i, M_i, S_i\)。

限制

  • \(1 \le H, W \le 1000\)
  • \(1 \le N \le 100\)
  • \(1 \le h_i, w_i \le 100\)
  • \(1 \le C_i \le 1000\)
  • \(1 \le M_i \le 100\)
  • \(1 \le S_i \le C_i\)
  • 保證至少有一種款式可依原方向完整鋪滿地面。

輸出格式

輸出一行,包含一個整數,代表完成鋪設的最小成本。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒,依正確通過的測試資料筆數給分。其中:

  • 第 1 子題組(\(60\) 分):\(N = 3\)。
  • 第 2 子題組(\(40\) 分):無額外限制。

範例輸入 1

4 6
3
2 3 10 20 3
2 2 8 8 2
1 6 30 3 10

範例輸出 1

60

範例解釋 1

若選擇第 \(2\) 種款式,需使用 \((4 / 2) \times (6 / 2) = 6\) 片磁磚,但最少要買 \(8\) 片。成本為 \(8 \times 8 - 2 \times 2 = 60\) 元,這是最小成本。

範例輸入 2

5 5
4
2 2 5 1 1
1 5 30 2 10
5 1 28 10 5
1 1 2 30 1

範例輸出 2

55

題目來源

APCS 2026 年 6 月初級實作題第 2 題。

題目頁說明

快速鍵

主要功能

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

限制

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