裝飲料 (APCS 2024-10 初級)

小夏買了杯冰水，想要裝進自備的冷飲杯中保持水的冰涼。杯子的內層空間為上下兩個長方體相接，下方的長方體底面為 \(w_1 \times w_1 ~\mathrm{cm^2}\) 的正方形，高為 \(h_1 ~\mathrm{cm}\)，上方的長方體底面為 \(w_2 \times w_2 ~\mathrm{cm^2}\) 的正方形，高為 \(h_2 ~\mathrm{cm}\)（如下圖）。

已知小夏買的 \(n\) 杯冰水體積分別為 \(V_1, V_2, \ldots, V_n\)（單位 ml，\(1 ~\mathrm{cm^3} = 1 ~\mathrm{ml}\)），請幫小夏計算此 \(n\) 杯冰水依序倒進杯中後，杯內的水每次增加的高度之最大值為何。請注意，此 \(n\) 杯冰水不一定能全部裝至冷飲杯中，杯子裝滿後高度即不再上升（即上升值為 \(0\)）。題目保證每次上升的高度必為整數。

舉例來說，若小夏買了 \(2\) 杯冰水，分別為 \(400 ~\mathrm{ml}\) 與 \(600 ~\mathrm{ml}\)。造型杯的規格為 \(w_1 = 5, w_2 = 10, h_1 = 12, h_2 = 8\)。裝入第一杯冰水時，下方的長方體會被裝滿（體積為 \(5 \times 5 \times 12 = 300\)），剩餘的 \(100 ~\mathrm{ml}\) 會在上方的長方體造成 \(1 ~\mathrm{cm}\) 的高度，故第一杯冰水裝入後杯中水上升的高度為 \(13 ~\mathrm{cm}\)。同理，第二杯冰水裝入後水位會由 \(13 ~\mathrm{cm}\) 上升至 \(19 ~\mathrm{cm}\)，高度增加了 \(6 ~\mathrm{cm}\)。兩次增加的高度分別為 \(13\) 與 \(6\)，故最大值為 \(13\)。

輸入格式

第一行有一個正整數 \(N\)（\(1 \le N \le 10\)），代表小夏買的冰水杯數。第二行有 \(4\) 個正整數，分別為 \(w_1, w_2, h_1, h_2\)（\(1 \le w_1, w_2, h_1, h_2 \le 50\)），且 \(w_1 < w_2\)，為冷飲杯的規格。第三行有 \(N\) 個正整數，代表小夏買的 \(N\) 杯冰水體積，每次加入水的體積不超過 \(10^4\)。同一行兩個數值間以一個空白間隔。

輸出格式

一個整數，為依序倒入此 \(N\) 杯冰水後冷飲杯中水增加的高度之最大值。

範例輸入 1

1
4 6 8 5
200

範例輸出 1

10

範例說明 1

僅有一杯水，倒入會注滿下方的長方體（\(4 \times 4 \times 8 = 128 ~\mathrm{ml}\)），剩餘的 \(72 ~\mathrm{ml}\) 會使上方長方體中的水位上升 \(2 ~\mathrm{cm}\)，上升高度為 \(10 ~\mathrm{cm}\)。

範例輸入 2

2
5 10 12 8
400 600

範例輸出 2

13

範例說明 2

此為題目中之範例。

範例輸入 3

4
5 10 12 30
400 600 2500 3000

範例輸出 3

23

範例說明 3

第一杯水上升 \(13 ~\mathrm{cm}\)，第二杯水上升 \(6 ~\mathrm{cm}\)，第三杯水加入後會超過杯子總容量（\(400 + 600 + 2500 = 3500 > 5 \times 5 \times 12 + 10 \times 10 \times 30 = 3300\)），加完後水的高度為 \(42 ~\mathrm{cm}\)，故第三杯水的上升高度為 \(42 - 19 = 23\)。第四杯水加入時杯子已滿，高度無任何改變。所以，最大上升高度為第三杯水的 \(23\)。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過測資筆數給分。其中：

• 第 1 子題組 60 分：\(N = 1\)。也就是只加一次水，算出注水後的高度即是答案。
• 第 2 子題組 40 分：無額外限制。

題目來源

APCS 程式實作初級題本範例，程式實作 2024 年 10 月。

• APCS 官方初級題本範例
• ZeroJudge o711