# APCS實作題2024年1月第3題：邏輯電路
> 日期：2024年2月22日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=m933)
## 題目
### 問題描述
請設計一個程式，模擬一個基本的邏輯電路系統。這個電路系統由數個輸入端口、邏輯閘和輸出端口組成，您需要模擬電路中的訊號傳遞與閘的運算求出所有輸出端口的數值，並計算整個電路的最大延遲時間。
電路包含以下元件：
- **輸入端口 (Input Ports)**：您將接收幾個二進制訊號，每個訊號的值為 0 或 1。這些訊號將用作電路的輸入。電路內共有 $p$ 個輸入端口，編號為 $1$ 到 $p$。
- **邏輯閘 (Logic Gates)**：有四種類型的邏輯閘，分別為 AND、OR、XOR 和 NOT 閘。這些閘接收輸入訊號，並根據其功能進行運算。電路內共有 $q$ 個邏輯閘，編號為 $p+1$ 到 $p+q$。各種邏輯閘的運算規則如下：
- **AND 閘 (AND gate)**：接收兩個輸入，如果兩個輸入皆為1，則輸出為1；否則輸出為0。
- **OR 閘 (OR gate)**：接收兩個輸入，如果至少有一個輸入為1，則輸出為1；如果兩個輸入皆為0，則輸出為0。
- **XOR 閘 (XOR gate)**：接收兩個輸入，如果兩個輸入不相同，則輸出為1；如果兩個輸入相同，則輸出為0。
- **NOT 閘 (NOT gate)**：僅接收一個輸入，並將其反轉。如果輸入為1，則輸出為0；如果輸入為0，則輸出為1。
- **輸出端口 (Output Ports)**：最終結果將會從這些端口輸出，每個端口對應著某些閘的輸出值。電路內共有 $r$ 個輸出端口，編號為 $p+q+1$ 到 $p+q+r$。
請模擬這個電路系統，確定每個閘的輸出值，以及計算整個電路的最大延遲時間，最大延遲時間即訊號從輸入端口傳遞到輸出端口可能經過最多邏輯閘的數量。
<br />
### 輸入說明
第一行包含四個整數，依序為 $p$、$q$、$r$、$m$。$p (1 \leq p \leq 10^3)$ 代表輸入端口的數量，$q (1 \leq q \leq 5 \times 10^4)$ 代表邏輯閘的數量，$r (1 \leq r \leq 10^3)$ 代表輸出端口的數量，而 $m$ 代表連接線的數量。
接下來一行有 $p$ 個整數 $v_1, v_2, \dots, v_p$，代表編號為 $1$ 到 $p$ 輸入端口的二進制值（0或1）。
接下來一行有 $q$ 個整數 $t_1, t_2, \dots, t_q$，代表編號為 $p+1$ 到 $p+q$ 的邏輯閘的類型（1為 AND、2為 OR、3為 XOR、4為 NOT）。
最後的 $m$ 行，每行包含兩個整數，代表連接線的起始端口和終端端口的編號。
每個輸入端口和邏輯閘的輸出會連到至少 $1$ 個至多 $20$ 個其他邏輯閘和輸出端口的輸入，且邏輯閘電路不會接出迴路。
**子題分數**：
- 40%：$p+q+r \leq 10^3$
- 60%：無限制
<br />
### 輸出說明
第一行輸出一個整數，表示計算出的特定端口的最大延遲時間，測試資料保證最大延遲不高過 $100$。
第二行輸出 $r$ 個二進制值（0或1），代表每一個輸出閘編號由小到大的輸出數值。
<br />
### 範例輸入1
```
4 5 4 13
1 0 1 0
1 2 3 4 1
1 5
2 5
2 6
3 6
3 7
4 7
4 8
5 10
6 9
6 11
7 9
8 13
9 12
```
### 範例輸出1
```
2
0 1 1 1
```
<br />
<img height="80%" width="80%" src="https://zerojudge.tw/ShowImage?id=3744" style="display: block; margin-left: auto; margin-right: auto;"/>
<br /><br />
### 範例輸入2
```
5 6 4 15
1 1 0 1 0
2 1 3 4 1 3
1 6
2 7
7 13
7 6
3 7
3 8
4 8
5 9
8 10
9 10
10 14
10 11
9 11
6 12
11 15
```
### 範例輸出2
```
3
1 0 1 0
```
<br />
<img height="80%" width="80%" src="https://zerojudge.tw/ShowImage?id=3756" style="display: block; margin-left: auto; margin-right: auto;"/>
<br /><br />
## Python 程式碼：由輸入到輸出
從吳邦一教授的解題講義〈[APCS 2024.01實作題題解 –- C++與Python](https://hackmd.io/eBZhK7HgSVa0AmAuD_VZxQ#%E7%AC%AC%E4%B8%89%E9%A1%8C-%E9%82%8F%E8%BC%AF%E9%9B%BB%E8%B7%AF-ZeroJudge-m933)〉看到的寫法。
費時最久約為 0.7 s，使用記憶體最多約為 23.8 MB，通過測試。
```python=
""" 由測資讀取資料 """
p, q, r, m = map(int, input().split()) # 讀取輸入端口數量 p、邏輯閘數量 q、輸出端口數量 r、連接線數量 m
n = p + q + r # 所有元件數量 n，元件編號為 1 ~ n，以下 5 項長度皆為 n+1
data = [0] + list(map(int, input().split())) + [0]*(q+r) # 每個節點的值，先加入輸入端口資料
gate = [0]*(p+1) + list(map(int, input().split())) + [0]*r # 每個邏輯閘種類
depth = [0]*(n+1) # 每個輸入端口對應的最大延遲時間，也就是前方的邏輯閘數量
pred = [[] for _ in range(n+1)] # 編號 i 節點的前置節點 (predecessor)
succ = [[] for _ in range(n+1)] # 編號 i 節點的後繼節點 (successor)
for _ in range(m): # 讀取連接線端點
u, v = map(int, input().split()) # 開頭 u、結尾 v
succ[u].append(v) # u 的後繼節點加入 v
pred[v].append(u) # v 的前置節點加入 u
""" 找出拓撲排序 topological sort """
indeg = [len(pred[v]) for v in range(n+1)] # 各節點的前置節點數量
seq = list(range(1, p+1)) # 待處理的節點編號，先放入輸入端口
head = 0 # 由 seq 讀取資料的索引值
while head < len(seq): # 當 head 未出界時繼續執行
v = seq[head] # 取出節點 v
head += 1 # head 加 1
for u in succ[v]: # 依序讀取 v 的後繼節點 u
indeg[u] -= 1 # 節點 u 的前置節點數量減 1
if indeg[u] == 0: seq.append(u) # 如果節點 u 已經沒有前置節點，將 u 加入 seq
""" 計算各節點狀態 """
for v in seq[p:]: # 由 seq 依序讀取節點 v，略過輸入端口
if gate[v] == 1: # AND
data[v] = data[pred[v][0]] & data[pred[v][1]]
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1
elif gate[v] == 2: # OR
data[v] = data[pred[v][0]] | data[pred[v][1]]
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1
elif gate[v] == 3: # XOR
data[v] = data[pred[v][0]] ^ data[pred[v][1]]
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1
elif gate[v] == 4: # NOT
data[v] = 1 - data[pred[v][0]]
depth[v] = depth[pred[v][0]] + 1
else: # output
data[v] = data[pred[v][0]]
""" 印出答案 """
print(max(depth)) # 印出最大延遲
print(*data[p+q+1:]) # 用解構運算子 * 將 data[p+q+1:] 拆開後印出
```
<br /><br />
## C++ 程式碼：由輸入到輸出
費時最久約為 66 ms，使用記憶體最多約為 7.3 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void myprint(vector<int> a) {
for(auto it = a.begin(); it != a.end(); it++)
cout << *it << " \n"[it == a.end()-1];
}
void myprint2(vector<vector<int>> a) {
for(auto it = a.begin(); it != a.end(); it++)
for(auto it2 = (*it).begin(); it2 != (*it).end(); it2++)
cout << *it2 << " \n"[it2 == (*it).end()-1];
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
/* 由測資讀取資料 */
// 讀取輸入端口數量 p、邏輯閘數量 q、輸出端口數量 r、連接線數量 m
int p, q, r, m; cin >> p >> q >> r >> m;
int n = p + q + r; // 所有元件數量 n，元件編號為 1 ~ n，以下 5 項長度皆為 n+1
// 每個節點的值，先加入輸入端口資料
vector<int> data (n+1, 0);
for(int i=1; i<=p; i++) {
int t; cin >> t;
data[i] = t;
}
// 每個邏輯閘種類
vector<int> gate (n+1, 0);
for(int i=p+1; i<=p+q; i++) {
int t; cin >> t;
gate[i] = t;
}
// 每個輸入端口對應的最大延遲時間，也就是前方的邏輯閘數量
vector<int> depth (n+1, 0);
// 編號 i 節點的前置節點 (predecessor) 及後繼節點 (successor)，先設定為空陣列
vector<vector<int>> pred (n+1), succ (n+1);
for(int i=0; i<m; i++) { // 讀取連接線端點
int u, v; cin >> u >> v; // 開頭 u、結尾 v
succ[u].push_back(v); // u 的後繼節點加入 v
pred[v].push_back(u); // v 的前置節點加入 u
}
/* 找出拓撲排序 topological sort */
vector<int> indeg; // 各節點的前置節點數量
for(auto pre : pred) indeg.push_back(pre.size());
vector<int> seq; // 待處理的節點編號，先放入輸入端口
for(int i=1; i<=p; i++) seq.push_back(i);
int head = 0; // 由 seq 讀取資料的索引值
while(head < seq.size()) { // 當 head 未出界時繼續執行
int v = seq[head]; head++; // 取出節點 v，head 加 1
for(int u : succ[v]) { // 依序讀取 v 的後繼節點 u
indeg[u]--; // 節點 u 的前置節點數量減 1
if (indeg[u] == 0) seq.push_back(u); // 如果節點 u 已經沒有前置節點，將 u 加入 seq
}
}
/* 計算各節點狀態 */
for(int i=p; i<seq.size(); i++) { // 由 seq 依序讀取節點 v，略過輸入端口
int v = seq[i];
if (gate[v] == 1) { // AND
data[v] = data[pred[v][0]] & data[pred[v][1]];
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1;
} else if (gate[v] == 2) { // OR
data[v] = data[pred[v][0]] | data[pred[v][1]];
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1;
} else if (gate[v] == 3) { // XOR
data[v] = data[pred[v][0]] ^ data[pred[v][1]];
depth[v] = max(depth[pred[v][0]], depth[pred[v][1]]) + 1;
} else if (gate[v] == 4) { // NOT
data[v] = 1 - data[pred[v][0]];
depth[v] = depth[pred[v][0]] + 1;
} else { // output
data[v] = data[pred[v][0]];
}
}
/* 印出答案 */
cout << *max_element(depth.begin(), depth.end()) << "\n"; // 最大延遲
for(int i=p+q+1; i<=n; i++) cout << data[i] << " \n"[i == n]; // 輸出端口
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet