# 2024/7/27 APCS 第七場模擬賽 題解

## AI 運算 (AI Operation)
> 出題者：Black_Lotus / Chung
> 難度：p1
> 考點：迴圈、陣列
### Statement
Black Lotus 剛開始學習神經網路，因此對神經網路的結構充滿好奇，想要自己嘗試實作一個簡單的模型。

神經網路由各個層組成，每層的裝置都有自己的輸入與輸出，而上一層的輸出必須與下一層的輸入相同才能進行運算。

但她不太知道最後實作出來的神經網路是否可以運作，因此希望你能夠寫一個程式，給定每個裝置的輸入與輸出，請檢查神經網路的每一層是否都可以進行正常運算。

### Input
輸入第一行有一個整數 $n\ (1 \le n \le 100)$ 代表有 $n$ 種不同的裝置。
接著有 $n$ 行輸入，每行有裝置的名稱 $m_i$ (只會是一個英文字母且保證不重複) 以及該裝置輸入與輸出的大小 $a_i,\ b_i\ (1 \le a_i,b_i \le 3)$。
接著一行有一個數字 $k\ (2 \le k \le 100)$，代表神經網路的層數。
最後一行有一個長度為 $k$ 的字串 $s$，分別代表每一層所使用的裝置名稱，第 $1$ 個字元代表第 $1$ 層的裝置名稱，以此類推。
### Output
請總共輸出 $k-1$ 行，每行輸出一個數字，假如第 $i$ 層的輸出等於第 $i+1$ 層的輸入請輸出 $1$，否則輸出 $0$。

### Testcase
- Input 1

3
A 2 1
B 1 3
C 3 1
5
ACBCA

- Output 1

0
1
1
0

### Subtask
- Subtask 1 (50%) - $k = 3$
- Subtask 2 (50%) - 無限制
### Note
- Input 說明
- $ACBCA$
- $A$ 的輸出 $\neq C$ 的輸入 -> 不合法
- $C$ 的輸出 $= B$ 的輸入 -> 合法
- $B$ 的輸出 $= C$ 的輸入 -> 合法
- $C$ 的輸出 $\neq A$ 的輸入 -> 不合法
- 所以輸出

            0
            1
            1
            0

### Solution
- 首先使用兩個陣列 $a,b$ 儲存輸入和輸出，因為字元本身就是一個數字，所以是可以用字元當作索引值的，又 'a' > 'A' 因此只要 $a,b$ 大小至少開到 'z' $+\ 1$，陣列就足夠大了。
- Subtask 1
- 因為 $k = 3$，所以我們可以把字串當成三個字元來看待，因此我們只需要讀入三個字元，再兩兩判斷輸入輸出是否相等即可。
- Subtask 2
- 我們可以從索引值 $i$ 從 $0$ 到 $n-2$ 遍歷字串，每次檢查 $i$ 跟 $i+1$ 的輸入輸出，再判斷輸入輸出是否相等即可。
### Code
- Subtask 1

#include<bits/stdc++.h>
using namespace std;
//declare
int n, a['z'+1], b['z'+1], k;
string s;
//
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        char c; cin>>c;
        cin>>a[c]>>b[c];
    }
    char x,y,z;
    cin>>k>>x>>y>>z;
    if(b[x] == a[y]) cout<<1<<"\n";
    else cout<<0<<"\n";
    if(b[y] == a[z]) cout<<1<<"\n";
    else cout<<0<<"\n";
    return 0;
}

- Subtask 2

#include<bits/stdc++.h>
using namespace std;
//declare
int n, a['z'+1], b['z'+1], k;
string s;
//
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        char c; cin>>c;
        cin>>a[c]>>b[c];
    }
    cin>>k>>s;
    for(int i=0;i<k-1;i++){
        if(b[s[i]] == a[s[i+1]]) cout<<1<<"\n";
        else cout<<0<<"\n";
    }
    return 0;
}

- Python

n = int(input())
d = {}
for _ in range(n):
    k, *o = input().split()
    d[k] = o
k = int(input())
s = input()
for i in range(k-1):
    if d[s[i]][1]==d[s[i+1]][0]:
        print(1)
    else:
        print(0)

print(*(lambda d,k,s:((d[s[i]][1]==d[s[i+1]][0])+0 for i in range(k-1)))({o[0]:o[1:] for o in (input().split() for _ in range(int(input())))},int(input()),input()),sep="\n")

## 小麥的螞蟻 (Wheat's ant)
> 出題者：小麥
> 難度：p2
> 考點：模擬
### Statement
有一天小麥養了一隻電動螞蟻，而這隻電動螞蟻只能在一張特殊的方格紙上運作。

一開始方格紙是全白的，並且螞蟻會在這一張紙的正中間並且頭部向 12 點鐘方向，然後開始按照下方的規則運作：

- 如果螞蟻所在的格子是白色，則把該格變成黑色，再沿原方向往前一格
- 如果移動過後螞蟻所在的格子還是白色，則把該格變成黑色，再順時針轉 90 度，然後沿原方向往前一格
- 如果螞蟻所在的格子是黑色，則逆時針轉 90 度，然後沿原方向往前一格
- 如果移動過後螞蟻所在的格子還是黑色，則把該格變成白色，再順時針轉 90 度，然後沿原方向往前一格

[影片](https://youtu.be/eXR4eD_oi5Q)

小麥想要問你在幾步之後這隻螞蟻會走出方格紙。如果超過 $10^6$ 步之後還是走不出去，請你輸出 "bad ant"（不含雙引號）。

小麥還想要知道在被走過的紙上有幾格是黑的，也麻煩你跟小麥說一下。
### Input
第一行包含兩個正整數 $n$、$m$。
- $n$ 代表紙的高度
- $m$ 代表紙的寬度

**題目測資範圍**
- $1 \leq n,m \lt 10^3$
- $n,m$ 為奇數
### Output
第一個輸出為螞蟻在幾步之後可以走出方格紙，如果走了 $10^6$ 步還是沒辦法，則輸出"bad ant"（不含雙引號）。
第二個輸出為方格紙上有幾個黑塊，就算走不出去也要告訴小麥。

### Testcase
- Input 1

7 7

- Output 1

30 21

- Input 2

867 497

- Output 2

bad ant 39211

### Subtask
| 分數 | 條件限制 |
|:----:|:------------------------:|
| 50% | $1 \leq n,m \leq 5$ |
| 50% | 題目測資範圍 |

### Solution

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
#define int long long

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<string> vs;
typedef vector<vs> v2s;
typedef vector<pii> vp;
typedef vector<vp> v2p;
typedef vector<bool> vb;
typedef vector<vb> v2b;

const vi move_x = {-1, 0, 1, 0};
const vi move_y = {0, 1, 0, -1};
int n, m;
v2i graph;
int white_counter = 0;
int black_counter = 0;
int heading = 0;

void turn_heading(int& heading, int rotation) {
	if (rotation == 0) {
		heading++;
		heading %= 4;
	}
	else {
		heading--;
		if (heading == -1) {
			heading = 3;
		}
	}
}

bool move(int& x, int& y) {
	if (graph[x][y] == 0) {
		black_counter = 0;
		if (white_counter == 0) {
			white_counter++;
			graph[x][y] = 1;
			x = x + move_x[heading];
			y = y + move_y[heading];
		}
		else {
			white_counter = 0;
			graph[x][y] = 1;
			turn_heading(heading, 0);
			x = x + move_x[heading];
			y = y + move_y[heading];
		}
	}
	else {
		white_counter = 0;
		if (black_counter == 0) {
			black_counter++;
			turn_heading(heading, 1);
			x = x + move_x[heading];
			y = y + move_y[heading];
		}
		else {
			black_counter = 0;
			graph[x][y] = 0;
			turn_heading(heading, 0);
			x = x + move_x[heading];
			y = y + move_y[heading];
		}
	}
	if (x >= n || x < 0 || y >= m || y < 0) {
		return false;
	}
	return true;
}

void solve() {
    cin >> n >> m;

	graph.resize(n, vi(m));

	int current_x = n / 2;
	int current_y = m / 2;

	int step = 0;
	while (step < 1e6) {
		step++;
		if (!move(current_x, current_y)) {
			break;
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (graph[i][j] == 1) {
				ans++;
			}
		}
	}

	if (step == 1e6) {
		cout << "bad ant " << ans << '\n';
	}
	else {
		cout << step << ' ' << ans << '\n';
	}
}

signed main() {
    fastio;
    solve();
    return 0;
}

- Python

def main():
    n,m = map(int,input().split())
    a = [[0]*m for _ in range(n)]
    x,y = n//2,m//2
    dx,dy = -1,0
    i = 0
    def o():
        return x<0 or y<0 or x>=n or y>=m
    while i < 1000000:
        i+=1
        if a[x][y]:
            dx,dy = -dy,dx
            x,y = x+dx,y+dy
            if o():
                break
            if a[x][y] and i<1000000:
                i+=1
                a[x][y] = 0
                dx,dy = dy,-dx
                x,y = x+dx,y+dy
        else:
            a[x][y] = 1
            x,y = x+dx,y+dy
            if o():
                break
            if not a[x][y] and i<1000000:
                i+=1
                a[x][y] = 1
                dx,dy = dy,-dx
                x,y = x+dx,y+dy
        if o():
            break
    else:
        print("bad ant 39211")
        return
    ans = sum(z for o in a for z in o)
    print(i, ans)
main()

## 題解
:::spoiler 50%
自己在紙上模擬，然後打表
:::
:::spoiler 100%
這個題目大概就是模擬而已，但題目有幾個非常值得探討的點：
1. 這題會用到在二維陣列題上非常經典的技巧，可以發現到在二維陣列上面只有「上、下、左、右」這四個方向，那其實就是往四個方向偏移，因此可以寫出下面的這個偏移量陣列，在移動的時候就可以用索引值的方式來移動
下方的範例 row 為 x，column 為 y

    vector<int> move_x = {-1, 0, 1, 0};
    vector<int> move_y = {0, 1, 0, -1};

2. 這題如果你是用上面的方式移動，就會發現到要一直維持頭轉的方向對應到偏移量是非常簡單的事，那又可以發現到其實頭轉的方向只有四個方向「12 點鐘、3 點鐘、6 點鐘、9 點鐘」，那在轉頭的時候可以做一個取模的動作，這樣就可以把目前頭的面向剛好對應到 $0 \sim 4$，就剛好是第一點對應的四個方向

取模的時候可能會有負的，但因為這裡的範圍比較小，所以可以用 if 的方式去判斷

    void turn_heading(int& heading, int rotation) {
        if (rotation == 0) {
            heading++;
            heading %= 4;
        }
        else {
            heading--;
            if (heading == -1) {
                heading = 3;
            }
        }
    }

:::

## L 的朋友圈 (L's Friends)
> 出題者：TLY
> 難度：p3
> 考點：動態規劃（Dynamic Programming）、二分搜
### Statement
L 喜歡擺爛，最喜歡的就是追劇、看動漫、看小說、打日麻，除了這四項以外的事情在她看來都是麻煩的，即便她喜歡挑簡單的事做，但她要做的事往往不會如她所想的簡單。

L 最好的朋友有時都說她太懶了，但 L 一直認為擺爛和懶是不一樣的，畢竟擺爛是她有做事，但不是正事，懶是什麼事都沒做。她最好的朋友都已經有些被她影響到了，於是她其他的朋友決定給她傳授正能量，結果最後她其他的朋友也被影響到了。

T 作為 L 的優質負責人，決定管理 L 的交友圈。T 收集了 L 交友圈其中 $n$ 位朋友內心的堅持度 $R$，以及 $n$ 位朋友的每小時被影響度 $C$。

每小時被影響度 $C$ 意味著 L 每傳達一次負能量給她的朋友，她的朋友內心的堅持度都會下降 $C$。不過 T 發現，因為 L 巨大的影響力，所以每位朋友的被影響度都是相等的，並且這些朋友內心的堅持度只會持續降低，不會有任何一位朋友的內心堅持度變高。

現在 T 想知道，就自己所知的資料來找，要讓 L 被最大連續能量影響的數值小於 $K$，這個時間最短可以是多少？

注意：時間都是以小時計算，這意味著 L 傳達負能量給朋友的同時，朋友也會傳達正（負）能量給她。朋友傳達給 L 的正（負）能量為當前朋友的內心堅持度（包含 L 同時間傳給朋友的負能量），最大連續能量為一段連續區間使得該區間內所有朋友的堅持度總和最大。L 傳達給朋友的負能量等同於朋友的被影響度，不論 L 被傳達多少能量都不會變更。

### Input
第一行包含三個整數 $n (1 \le n \le 1.5×10^5), K(1 \le K \le 10), C(1 \le C \le 10)$
第二行包含 $n$ 個整數 $R_i(-10^9 \le R_i \le 10^9)$
### Output
輸出一個整數，代表達成最大連續能量小於 $K$ 的最短時間。
### Testcase
- Input 1

5 8 1
2 4 1 2 9

- Output 1

3

- Input 2

9 3 9
3 -7 2 0 1 4 -9 2 -12

- Output 2

1

### Subtask
- Subtask 1 (30%) - $1 \le n \le 10000, -10^4 \le R_i \le 10^4$
- Subtask 2 (70%) - 無特殊限制
### Note

### Solution
<!-- 給定 L 交友圈其中 $n$ 位朋友內心初始的堅持度 $R$，還有這些朋友的每小時被影響度 $C$。然後因 L 巨大的影響力，所以每位朋友的被影響度都是相等的。
這題的時間是以小時計算的，所以 L 每小時都會給朋友傳達負能量，每傳達一次負能量這個朋友的內心堅持度就會下降 $C$。
然後做為 L 負責人的 T 想知道要讓 L 被最大連續能量影響的數值小於 $K$，所花的時間最短可以是多少。 -->
- 定義一個用於計算 `L 被最大連續能量影響的數值` 的函式，也就是用來計算最大連續和的函式，函式內部使用動態規劃中的 `卡丹算法` 進行計算。（也可以直接寫在主函式的迴圈中）
- Subtask 1
- 直接使用 for 迴圈從 0 開始循序搜尋
- $O(n \times R_i)$
- Subtask 2
- 使用二分搜尋法進行搜尋
- $O(n \log R_i)$
### Code
- Subtask 1

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
using namespace std;
ll n, K, C, maxR = LONG_LONG_MIN, i, rtn, sum, ans;
vector < ll > R;
ll T_search(ll Time) {
    rtn = 0;
    for (i = 1; i <= n; i++) sum = (i == 1 ? (R[i] - (C * Time)) : max(0ll, sum + (R[i] - (C * Time)))), rtn = max(rtn, sum);
    return rtn;
}
int main() {
    fastio;
    cin >> n >> K >> C, R.resize(n + 1);
    for (i = 1; i <= n; i++) cin >> R[i];
    for (ll i = 0; ; i++) if (T_search(i) < K) { ans = i; break; }
    cout << ans << "\n";
    return 0;
}
// 原code來源: 偉大的Chung教授

- Subtask 2 - By Chung

#include<bits/stdc++.h>
#define int long long
using namespace std;
//declare
int n,k,c;
vector<int> v;
//
int compute(int mid){
    int sum = 0, mx = 0;
    for(int i=0;i<n;i++){
        sum = max(0ll, sum + (v[i] - c*mid));
        mx = max(mx, sum);
    }
    return mx;
}
signed main(){
    cin>>n>>k>>c;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
    }
    int L = 0, R = 1e9;
    while(R-L > 1){
        int mid = (L+R) / 2;
        if(compute(mid) < k) R = mid;
        else L = mid;
    }
    cout<<R<<"\n";
    return 0;
}

- Subtask 2 - By TLY

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
using namespace std;
ll n, K, C, maxR = LONG_LONG_MIN, i, rtn, sum, mid, run;
constexpr ll maxn = 150000;
vector < ll > R(maxn + 1);
ll T_search(ll Time) {
    rtn = LONG_LONG_MIN;
    for (i = 1; i <= n; i++) sum = (i == 1 ? (R[i] - (C * Time)) : max(0ll, sum + (R[i] - (C * Time)))), rtn = max(rtn, sum);
    return rtn;
}
int main() {
    fastio;
    cin >> n >> K >> C;
    for (i = 1; i <= n; i++) cin >> R[i], maxR = max(maxR, abs(R[i]));
    ll L = 0, R = maxR * n;
    while (L + 1 < R) mid = (L + R) >> 1 , run = T_search(mid), ((run >= K) ? L = mid : R = mid);
    cout << R << "\n";
    return 0;
}

- Python

def main():
    n,k,c = map(int,input().split())
    a = list(map(int,input().split()))
    l = 0
    r = 10**9
    while l<r:
        m = (l+r)//2
        x = y = z = 0
        for i in range(n):
            x += a[i] - m*c
            y = min(x,y)
            z = max(z,x-y)
        if z<k:
            r = m
        else:
            l = m+1
    print(l)
main()

- Python bisect (使用部分新版本功能，實際APCS不可用)

import bisect
def main():
    n,k,c = map(int,input().split())
    a = tuple(map(int,input().split()))
    def f(m):
        x = y = z = 0
        for i in range(n):
            x += a[i] - m*c
            y = min(x,y)
            z = max(z,x-y)
        return -z
    print(bisect.bisect(range(10**9),-k,key=f))
main()

print((lambda n,k,c,b:__import__("bisect").bisect(range(10**9),-k,key=lambda m:(lambda l:-max(l.__setitem__(0,min(x,l[0])) or x-l[0] for x in (v-(i+1)*m*c for i,v in enumerate(b))))([0])))(*map(int,input().split()),list(__import__("itertools").accumulate(map(int,input().split())))))

## 滑雪道（Ski Runs）

> 出題者：Ting
> 難度：4
> 考點：貪心、動態規劃

### Statement

有一座山有 $N$ 個山峰，第 $i$ 個山峰高度為 $h_i$（$1 \leq i \leq N$），山峰之間的高度視為線性。

精通滑雪的 Chung 教授想把這座山規劃為滑雪場，做法是將山峰間的區域劃分為滑雪道和休息區兩種，每個相鄰山峰間可以為滑雪道或休息區，兩種區域會交替出現，例如下圖：


圖中，黑點代表山峰，灰色區域為休息區，其餘顏色均為滑雪道。

不過，設立滑雪道和休息區都具有成本，其中：

- 滑雪道的成本按段計算（連續即視為同一段），一段的成本為其左右兩端的高度差，亦即包含編號 $l$ 到 $r$ 山峰（含端點）的滑雪道造成的成本為 $\lvert h_l - h_r \rvert$。
- 休息區的成本按個計算（連續視為獨立的數個），一個的成本為其左右的山峰中較高者的高度，亦即在編號 $i$ 和 $i + 1$ 山峰間的休息區造成的成本為 $\max(h_i, h_{i + 1})$。

而規劃一座山的總成本即為滑雪道和休息區設立成本的總和。

並且，為了安全考量，每段滑雪道中的高度必須滿足非嚴格單調的條件，亦即若一段滑雪道包含了編號 $l$ 到 $r$ 的山峰，則須滿足 $h_i \leq h_j \space \forall \space l \leq i < j \leq r$ 或 $h_i \geq h_j \space \forall \space l \leq i < j \leq r$ 其一。

Chung 教授想請精通程式設計的你幫忙，計算將給定的山規劃為滑雪場所須的最小成本。

### Input

第一行包含一個數字 $N$，滿足 $2 \leq N \leq 10^6$。

第二行包含 $N$ 個數字 $h_1 \space h_2 \space \dots \space h_N$，滿足 $0 \leq h_i \leq 1000$。

### Output

輸出一個數字表此情況下的最小成本。

### Testcase

- Input

7
1 3 4 2 8 7 5

- Output

18

### Subtask

- Subtask 1 (20%) - $N \leq 16$
- Subtask 2 (80%) - $N \leq 10^6$

### Solution

- Subtask 1

對於每個山峰間為滑雪道或休息區二元枚舉，遍歷檢查非嚴格單調的條件，複雜度為 $\mathcal{O}(2^N \cdot N)$。

或是也可以一邊遞迴枚舉一邊檢查，複雜度為 $\mathcal{O}(2^N)$。

- Subtask 2

定義動態規劃狀態：

- $dp[i][0]$ 表考慮前 $i$ 個山峰，編號 $i$ 和 $i - 1$ 山峰間的高度為非嚴格遞增時的最小成本。
- $dp[i][1]$ 表考慮前 $i$ 個山峰，編號 $i$ 和 $i - 1$ 山峰間的高度為非嚴格遞減時的最小成本。

即可按照當前山峰和上一個山峰的高度關係進行轉移，所求為 $\min(dp[n][0], dp[n][1])$。

### Code

- Subtask 1

#include <bits/stdc++.h>

using namespace std;

const int Max = 2e9;

int main ()
{
  int n;
  cin >> n;

  vector<int> h (n);
  for (int &i : h) cin >> i;

  int ans = Max;
  for (int i = 0; i < 1 << (n - 1); i++)
    {
      int state = 0, k = 0, now = 0;
      for (int j = 0; j < n - 1; j++)
        {
          if (i >> j & 1)
            {
              now += abs (h[j] - h[k]) + max (h[j], h[j + 1]);
              state = 0, k = j + 1;
              continue;
            }
          if ((state == 1 && h[j] > h[j + 1]) ||
              (state == 2 && h[j] < h[j + 1]))
            {
              now = Max;
              break;
            }
          if (h[j] != h[j + 1]) state = h[j] < h[j + 1] ? 1 : 2;
        }
      ans = min (ans, now + abs (h[n - 1] - h[k]));
    }
  cout << ans << '\n';

  return 0;
}

- Subtask 2

#include <bits/stdc++.h>

using namespace std;

int main ()
{
  int n;
  cin >> n;

  vector<int> h (n);
  for (int &i : h) cin >> i;

  vector<array<int, 2>> dp (n);
  for (int i = 1; i < n; i++)
    {
      dp[i][0] = dp[i][1] = max (h[i], h[i - 1]) + min (dp[i - 1][0], dp[i - 1][1]);

      if (h[i] >= h[i - 1]) dp[i][0] = min (dp[i][0], dp[i - 1][0] + h[i] - h[i - 1]);
      if (h[i - 1] >= h[i]) dp[i][1] = min (dp[i][1], dp[i - 1][1] + h[i - 1] - h[i]);
    }
  cout << min (dp[n - 1][0], dp[n - 1][1]) << '\n';

  return 0;
}

- Python

def main():
    n = int(input())
    a = map(int,input().split())
    dp0 = 0
    dp1 = 0
    prev = next(a)
    for i in range(1,n):
        cur = next(a)
        nw = max(cur,prev)+min(dp0,dp1)
        if prev<=cur:
            dp0 = min(nw,dp0+cur-prev)
        else:
            dp0 = nw
        if prev>=cur:
            dp1 = min(nw,dp1+prev-cur)
        else:
            dp1 = nw
        prev = cur
    print(min(dp0,dp1))
main()