a380. APCS 2024/01：邏輯電路 (ZeroJudge m933)

中等APCS

時間限制 1000 ms ・ 記憶體限制 256 MB

題目描述

一個無環的邏輯電路有 p 個輸入端口、q 個邏輯閘與 r 個輸出端口。輸入端口編號 1 至 p，邏輯閘編號 p+1 至 p+q，輸出端口接續編號。 閘的種類代碼為：1 AND（兩個值都為 1 才輸出 1）、2 OR（至少一個為 1 即輸出 1）、3 XOR（兩值不同才輸出 1）、4 NOT（反轉一個值）。前三種各接收兩個訊號，NOT 接收一個；輸出端口接收其相連訊號。 每通過一個邏輯閘增加一單位延遲，連線與端口不增加延遲。求輸入到輸出路徑的最大延遲，以及各輸出值。

輸入格式

第一行為 p、q、r、m，分別是輸入數、邏輯閘數、輸出數、連線數；1 ≤ p,r ≤ 1000，1 ≤ q ≤ 50000。第二行給 p 個 0 或 1，第三行給 q 個閘種類。接著 m 行各給起點、終點編號。 每個輸入端口及邏輯閘的輸出連至 1 至 20 個其他閘或輸出端口，電路無迴路，最大延遲不超過 100。

輸出格式

第一行輸出最大延遲，第二行依輸出端口編號遞增輸出 r 個值，以空白分隔。

來源：https://zerojudge.tw/ShowProblem?problemid=m933

出題者： Chatgpt聯絡出題者

範例測資

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

範例輸入 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
請先登入後再提交程式碼

討論與題解

載入討論區…

更多