APCS實作題2024年10月第1題：裝飲料

# APCS實作題2024年10月第1題：裝飲料 > 日期：2024年10月25日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o711) ## 題目 ### 問題描述有一個杯子，可將其體積視為由兩個長方體組成（如下圖），下方的長方體底面積為 $w_1 \times w_1 ~\mathrm{cm^2}$，高為 $h_1 ~\mathrm{cm}$，上方的長方體底面積為 $w_2 \times w_2 ~\mathrm{cm^2}$，高為 $h_2 ~\mathrm{cm}$。 <img style="display: block; margin-left: auto; margin-right: auto" height="30%" width="30%" src="https://zerojudge.tw/ShowImage?id=4313"> 一開始杯子為空。要裝 $n$ 次飲料，每一次裝 $v ~\mathrm{cm^3}$ 容量的飲料，當水杯滿時水位不再上升。問這 $n$ 次倒飲料中水位上升變化量最高是幾 cm。 ### 輸入格式第一行有一個正整數 $n$ 代表要裝 $n ~(1 \leq n \leq 10)$ 次飲料。接下來一行有 $4$ 個正整數 $w_1, w_2, h_1, h_2 ~(1 \leq w_1, w_2, h_1, h_2 \leq 50)$ 代表杯子的寬度與高度。最後一行有 $n$ 個正整數代表每次裝飲料的容量。保證每次水位上升都是整數。子題配分 - 60%：$n = 1$，即答案為倒水後的高度 - 40%：無限制 ### 輸出格式輸出這 $n$ 次倒水中，上升變化量最大的高度為何。 ### 範例輸入1 ``` 1 4 6 8 5 200 ``` ### 範例輸出1 ``` 10 ``` ### 範例輸入2 ``` 2 5 10 12 8 400 600 ``` ### 範例輸出2 ``` 13 ``` ### 範例輸入3 ``` 5 16 44 28 17 2560 1280 1536 1024 10448 ``` ### 範例輸出3 ``` 10 ``` ## Python 程式碼費時最久約 21 ms，使用記憶體最多 3.3 MB，通過測試。 ```python= n = int(input()) # 倒飲料次數 n w1, w2, h1, h2 = map(int, input().split()) # 底面寬度、高度 a1, a2 = w1*w1, w2*w2 # 下半部、上半部截面積 v1, v2 = a1*h1, a2*h2 # 下半部、上半部容積 data = list(map(int, input().split())) # n 次倒飲料的體積 imax, h, tot = 0, 0, 0 # 上升高度最大值、總高度、總體積 for d in data: # 依序由 data 讀取資料 dh = 0 # 這個倒飲料的高度變化 tot += d # 更新總體積 if tot <= v1: # 如果總體積小於等於 v1，倒入飲料後還在下半部 dh = d // a1 # 計算 dh else: # 倒入飲料後已經在上半部 if h <= h1: # 原來在下半部 tmp = a1*(h1-h) # 於下半部的上升的高度 dh = (h1-h) + (d-tmp)//a2 # 加上於上半部上升的高度 else: # 已經在上半部 dh = d // a2 # 計算 dh if tot >= v1 + v2: # 如果杯子已裝滿 dh = h1 + h2 - h h += dh # 更新總高度 imax = max(imax, dh) # 更新最大值 # end of for loop print(imax) # 印出最大值 ``` ## C++ 程式碼費時最久約 2 ms，使用記憶體最多 352 kB，通過測試。 ```cpp= #include <iostream> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; // 倒飲料次數 n int w1, w2, h1, h2; cin >> w1 >> w2 >> h1 >> h2; // 底面寬度、高度 int a1 = w1*w1, a2 = w2*w2; // 下半部、上半部截面積 int v1 = a1*h1, v2 = a2*h2; // 下半部、上半部容積 int data[n]; for(int i=0; i<n; i++) cin >> data[i]; // n 次倒飲料的體積 int imax =0, h = 0, tot = 0; // 上升高度最大值、總高度、總體積 for(int i=0; i<n; i++) { // 依序由 data 讀取資料 int dh = 0, d = data[i]; // 這次倒飲料的高度變化 tot += d; // 更新總體積 if (tot <= v1) { // 如果總體積小於等於 v1，倒入飲料後還在下半部 dh = d / a1; // 計算 dh } else { // 倒入飲料後已經在上半部 if (h <= h1) { // 原來在下半部 int tmp = a1*(h1-h); // 於下半部的上升的高度 dh = (h1-h) + (d-tmp)/a2; // 加上於上半部上升的高度 } else { // 已經在上半部 dh = d / a2; // 計算 dh } if (tot >= v1 + v2) dh = h1 + h2 - h; // 如果杯子已裝滿 } h += dh; // 更新總高度 if (dh > imax) imax = dh; // 更新最大值 } cout << imax << "\n"; // 印出最大值 return 0; } ``` --- ###### tags:`APCS`、`Python`、`C++`