# 2024/10 APCS 實作題

# 第一題 - 裝飲料
:::info
https://zerojudge.tw/ShowProblem?problemid=o711
:::

## 題目
有一個杯子，可將其體積視為由兩個長方 體組成（如下圖），下方的長方體底面積 為 $w_1 \times w_1$ cm$^2$，高為 $h_1$ cm，上方的長方體底面積為 $w_2 \times w_2$ cm$^2$，高為 $h_2$ cm。
一開始杯子為空。要裝 $n$ 次飲料，每一次裝 $v$ cm$^3$ 容量的飲料，當水杯滿 時水位不再上升。問這 $n$ 次倒飲料中水位上升變化量最高是幾 cm。

## 輸入說明:
第一行有一個正整數 $n (1 \le n \le 10)$ 代表要裝 $n$ 次飲料。接下來一行有 4 個正整數 $w_1, w_2, h_1, h_2 (1 \le w_1, w_2, h_1, h_2 \le 50)$ 代表杯子的寬度與高度。最後一行有 $n$ 個正整數代表每次裝飲料的容量。保證每次水位上 升都是整數。
(60%) n = 1，即答案為倒水後的高度
(40%) 無限制

## 輸出說明:
輸出這 $n$ 次倒水中，上升變化量最大的高度為何。
## 解題絲路
說實話其實我一開始根本看不懂題目...講來講去到底要幹嘛還是不清楚，光是讀懂題目就花了一段時間...

白話文:
杯子的體積是一大一小兩個長方形體積相加，連續倒n次水，哪次會使水位升高最多(溢出的就不算)。
>
> 以測資2舉例:
> 第一次倒 400：水位從 0 → 13（上升 13）
> 第二次倒 600：水位從 13 → 19（上升 6）
> 輸出13。

所以想法其實很簡單，就只有三種情況:
1. **V<=G1**: 如果此時倒水體積(V)小於小長方體(G1)，那增加的高度就只有 $(V/G1)\times h1$
2. **G1<=V<=G2+G1**: 如果此時的體積(V)大於G1卻小於G2，則增加高度為$h1 + ((V-G1)/G2)\times h2$
3. **G1+G2<V**: 如果此時的體積(V)大於G1+G2也就是大於整個杯子，則水會溢出來，$h1 + h2$

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int main(){

    int n;
    cin >> n;

    double w1,w2,h1,h2;
    cin >> w1>> w2>>h1>>h2;

    double G1 = w1*w1*h1;
    double G2 = w2*w2*h2;

    double mx=0,V=0,H=0;
    for (int i=0;i<n;++i){
        double a;
        cin >> a;

        double oldH=H;
        V+=a;
        
        if (V <= G1)H=V/G1*h1;
        else if (V <= G1 + G2) H = h1 + (V - G1) / G2*h2;
        else H=h1+h2;

        mx = max(mx, H-oldH);
    }
    cout << mx;
}

:::warning
因為C++除法的特性，所以建議都用double。
:::

# 第二題 - 蒐集寶石
2024/10 實作第二題
:::info
題目:
{%preview https://zerojudge.tw/ShowProblem?problemid=o712 %}
:::
# 題目
有一個 $M \times N$ 的地圖，每一格的數字紀錄著寶石的數量，如果數字是 -1 代表牆壁。
有一位機器人一開始位於 $(r, c)$ 的位置上且方向朝右邊，他遵循著以下規則行走。
1. 若機器人位於的格字內寶石數量為 $0$，則機器人程式終止。
2. 機器人維護著一個分數 score，將 score 加上當前格的寶石數量，並且撿起一顆寶石。
3. 若 score 是 $k$ 的倍數，則向右轉 90 度。
4. 若機器人面向的格子是牆壁或是超出邊界，則繼續向右轉 90 度直到面向的格子非牆壁或非超出邊界，並回到第 1 步。

例如機器人一開始在座標 $(2, 1)$ 且 $k = 2$，向右走兩步之後分數為 $3 + 2 + 3 = 8$， 由於 $8$ 是 $2 (k = 2)$ 的倍數所以向右轉 $90$ 度。接下來往下走一步分數變為 $11$，需要向右轉 $2$ 次 $90$ 度才不會面向牆壁或是邊界外的格子。
接下來向前走一步走到座標 $(2, 3)$，由於先前已經拿走一顆寶石，該位置的寶石數量變為 $2$，因此分數變為 $13$，再繼續往上走兩步到 $(0, 3)$ 處分數為 $16$，由於 $16$ 為 $2 (k = 2)$ 的倍數所以向右轉 $90$ 度。
向前走一格到 $(0, 4)$ 後需要向右轉兩次 $90$ 度，回到 $(0, 3)$ 後由於寶石數量為 $0$ ，機器人停止。過程中機器人總共撿了 $8$ 顆寶石。

## 輸入說明:
第一行有 $5$ 個正整數 $M, N, k, r, c$
$1 \le M \le 100$
$2 \le N \le 100$
$1 \le k \le 20$
$0 \le r < m$
$0 \le c < n$
保證機器人初始位置不是牆壁。接下來有 $M$ 行，每一行有 $N$ 的數字，代表地圖的資訊。
(60%) M = 1
(40%) 無限制

## 輸出說明:
輸出機器人會蒐集幾個寶石。

---
格狀圖的應用，只要記得下面這幾件事:
1. 用moves代表移動，dir來實現移動。
2. 結束條件多-> 用另一個函式來判斷是否符合結束條件。
3. 因為要一直執行，用無限迴圈。
4. 用原生array建立格狀圖

## 初步格式

# include <bits/stdc++.h>
# define io ios::sync_with_stdio(0),cin.tie(0);
using  namespace std;

int graph[101][101] ={};
int moves[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int end(){} // 如果要結束就回傳 1

int main(){io;
    memset(graph,-1,sizeof(graph));
    // 因為有預留牆壁的位置所以迴圈從1開始跑
    for (int i=1;i<=M;++i){
	for (int j=1;j<=N;++j){
		cin >> graph[i][j];
        }
    }
    int score=0,gem=0;
    
    while(true){
        if (end())break;
        if (!(score%k))dir=(dir+1)%4;
    }
    
    
    return 0;
}

:::warning
要注意因為有給牆壁留空間，所以起始位置各要++
:::
**轉彎規則如下:**
1.score是k倍數。
2.面向牆壁要無條件一直轉，直到不是面向牆壁。

所以除了上面程式寫到的`if (!(score%k))dir=(dir+1)%4;`，我們還ˊ需要另一個while來一直判斷此時是否面向牆壁。

## 解

# include <bits/stdc++.h>
# define io ios::sync_with_stdio(0),cin.tie(0);
using  namespace std;

int graph[102][102] ={};
int moves[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int end(int r,int c){
    if (graph[r][c]==0)return 1;

    int ok=4;
	for (int i=0;i<4;i++)  //判斷四面是否都是牆壁
		if (graph[r+moves[i][0]][c+moves[i][1]] == -1)
			ok--;

	if (ok == 0)  //四面都是牆壁
		return 1;

	return 0;
}
int main(){io;
    int M,N,k,r,c;
    cin >> M >> N >> k>>r>>c;

    memset(graph,-1,sizeof(graph));

    // 因為有預留牆壁的位置，所以起始位置要++
    r++;
    c++;


	for (int i=1;i<=M;++i){
		for (int j=1;j<=N;++j){
			cin >> graph[i][j];
        }
	}

    int score=0,gem=0,dir=0;

    while (true){
        if (end(r,c))break;

        score+=graph[r][c];
        graph[r][c]--;
        gem+=1;

        if (!(score%k))dir=(dir+1)%4;

        int temp_r,temp_c;
        while (true){
            // 如果現在的方向是面對牆壁，要轉到正確的方向
            temp_r = r+moves[dir][0];
            temp_c = c+moves[dir][1];
            if (graph[temp_r][temp_c]==-1)dir=(dir+1)%4;
            else break;
        }
        r = temp_r;
        c = temp_c;
    }
    cout << gem;
    return 0;
}

---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!

**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。