(2024年1月APCS大學程式設計先修檢測題目：Netlist Simulator)
▌晶片模擬軟體是什麼？重要嗎？
主要是用軟體來驗證所設計電路的正確性
試想，要是手機晶片出錯、遊戲打到一半當機心情一定很糟吧
因此，模擬軟體是十分重要的！
業界常見的晶片電路模擬軟體為：NC-Verilog、VCS、Spice等
個人則可以使用一些開源軟體，如：Verilator、iverilog等
▌APCS：大學入學程式加分題
APCS全名為「大學程式設計先修檢測」，由台師大執行、教育部指導
近來台灣有越來越多大學校系都採計APCS成績，是國家層級認可的考試
例如：台清交資工系都有APCS組、成大電機系也有APCS組
在APCS考得好，可有效對審查委員證明自己的程式能力
▌APCS 2024/1 實作第三題：Netlist Simulator
這題給定一個數位電路的設計Netlist與輸入數值，希望求出：
1) 電路對應會輸出的結果 (Output results)
2) 算出從輸入到輸出最多會經過幾個邏輯閘 (Number of gates on critical path)
這題蘿蔔真的覺得很有趣
寫出來的軟體可以用來執行晶片設計流程中的 Gate-level Simulation
因此我們認為題目的實用性蠻高，出得很好！
Zero Judge連結：https://reurl.cc/YVq5p0
也歡迎大家利用空閒時間一起來玩玩看！
▌演算法思路提示
Hint：可以用DFS or BFS or Topological Sort來解
簡單說，可以想成要把值從輸入「傳播」到輸出
剛開始某個邏輯閘的輸入可能是沒有值的，此邏輯閘就「不能傳播」輸入值到輸出
當邏輯閘的所有的輸入都有值了，此邏輯閘就「可傳播」輸入值到輸出
具體有三步：
1) 將「可傳播」的邏輯閘存到一個Queue裡
2) 每次取出其中一個邏輯閘，算出對應的輸出值 (e.g., 1 AND 0 = 0)
3)把輸出值傳播給下一級邏輯閘的輸入，對應更新最長邏輯路徑長度
當這個Queue是空的時候，答案就會找出來了！
▌索取免費圖像化詳解
筆者自己也嘗試解過這一題，有通過Online Judge了
但真心覺得國高中就寫的出這題好厲害，給讚！
如果對於這題的免費詳解有興趣，或之後也想考APCS的同學家長們
歡迎到以下的Google表單填寫email，領取我們精心準備的圖像化詳解以及對應的程式碼：
https://forms.gle/ZkRPeddT3kDmRHaR9
我們會盡快寄出！(蘿蔔最近較忙，若慢了一些請見諒
▌參考資料
- APCS採計大學校系：https://apcs.csie.ntnu.edu.tw/index.php/apcs-introduction/gradeschool/
- APCS檢定是什麼：https://reurl.cc/eLybpW
- 政大資訊系 Gate-level Simulation：https://www.cs.nccu.edu.tw/~whliao/ds2003/VHDL.htm