m933. 3. 邏輯電路 - 高中生程式解題系統

內容

請設計一個程式，模擬一個基本的邏輯電路系統。這個電路系統由數個輸入端口、邏輯閘和輸出端口組成，您需要模擬電路中的訊號傳遞與閘的運算求出所有輸出端口的數值，並計算整個電路的最大延遲時間。

電路包含以下元件：

輸入端口（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$。

請模擬這個電路系統，確定每個閘的輸出值，以及計算整個電路的最大延遲時間，最大延遲時間即訊號從輸入端口傳遞到輸出端口可能經過最多邏輯閘的數量。

輸入說明

第一行包含四個整數，依序為 $p、q、r、m$。$p(1 \le p \le 10^3)$ 代表輸入端口的數量，$q(1 \le q \le 5 \times 10^4$ 代表邏輯閘的數量，$r(1 \le r \le 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 \le 10^3$
60%: 無限制

輸出說明

第一行輸出一個整數，表示計算出的特定端口的最大延遲時間，測試資料保證最大延遲不高過 $100$。
第二行輸出 $r$ 個二進制值（0 或 1），代表每一個輸出閘編號由小到大的輸出數值。

範例輸入 #1

範例輸出 #1

2
0 1 1 1

範例輸入 #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

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

範例 1 解釋：

範例 2 解釋:

標籤:

出處:

2024年1月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
39059	toseanlin@gm ... (Dr. SeanXD)	m933	圖文詳解＋解題思路	636	2024-01-10 11:08
39485	youtong826 (Youtong0826)	m933	dfs+dp	225	2024-02-27 03:14
39034	sophie198205 ... (闕河正)	m933	BFS詳解	493	2024-01-08 21:56
39483	a302854888@g ... (小麥)	m933	兩種解法	134	2024-02-26 21:38
39092	nonamegogo (nonamegogo)	m933	類似拓撲排序(Topological Sort)，也可以看成BFS	289	2024-01-12 23:20