磁磚拼貼 (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 題。