在為機器人實作電路時,你發現了一些異常。機器人可能會執行 $N = 128$ 個程式,編號從 $0$ 到 $N-1$。通常情況下,在任何時刻都應該只有一個程式(在 $N$ 個程式中)正在執行。然而,由於某些未知原因,有時會恰好有三個程式同時執行。幸運的是,作為一名經驗豐富的程式設計師,你知道如何處理這種情況,並決定實作一個電路來偵測此類異常。
你首先建立 $N$ 個輸入。若第 $i$ 個程式未執行,則第 $i$ 個輸入為 $0$,否則為 $1$。接著,你加入邏輯閘,其編號從 $N$ 開始連續遞增。每個邏輯閘可以接收特定數量的輸入,並產生單一輸出($0$ 或 $1$)。 第 $i$ 個邏輯閘的輸入可以是任何編號小於 $i$ 的邏輯閘之輸出,或是最初的 $N$ 個輸入之一。
邏輯閘共有三種類型:
NOT:接收恰好一個輸入。若輸入為 $0$,則輸出為 $1$,否則輸出為 $0$。OR:接收恰好兩個輸入。若兩個輸入皆為 $0$,則輸出為 $0$,否則輸出為 $1$。AND:接收恰好兩個輸入。若兩個輸入皆為 $1$,則輸出為 $1$,否則輸出為 $0$。
若偵測到異常(即前 $N$ 個輸入中恰好有三個為 $1$),則最後一個邏輯閘的輸出應為 $1$;若前 $N$ 個輸入中恰好有一個為 $1$,則輸出應為 $0$。
保證前 $N$ 個輸入中 $1$ 的數量恰好為一個或恰好為三個。
實作細節
你必須寫出一個輸出檔案,描述一個適用於 $\color{red}{N = 128}$ 的有效電路。
輸出檔案的第一行應包含一個整數,代表所使用的邏輯閘數量。
其餘每一行應為以下三種格式之一:
NOT in_1 OR in_1 in_2 AND in_1 in_2
每一行分別代表新增一個 NOT、OR 或 AND 邏輯閘。對於 NOT,in_1 是該邏輯閘的輸入編號。對於 OR 和 AND,in_1 和 in_2 是該邏輯閘的輸入編號。在第一行之後,第 $i$ 行所新增的邏輯閘編號為 $N-1 + i$。
邏輯閘總數不得超過 $1024$。換句話說,輸出檔案的總行數不得超過 $1025$。
子任務
- (100 分) 無額外限制。
評分
對於每個子任務,若電路無法通過任何測試案例,你的得分將為 $0$。
否則,令 $K$ 為電路所使用的邏輯閘數量。你的得分將為 $f(K) \times$ [該子任務的分數],其中:
$$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$$
圖 1:針對每個 K 值的任務得分
你必須將你的解法寫入輸出檔案 1.out,然後將輸出檔案壓縮成一個 .zip 檔案並提交該 .zip 檔案。
範例
考慮一個簡化版的任務,其中 $N = 4$(請注意,你只需要提供 $N = 128$ 的解法)。一個可能的解法是建立以下電路:
3 OR 0 1 OR 2 3 AND 4 5
該電路包含:
- 邏輯閘 $4$,若輸入 $0$ 或 $1$ 中至少有一個為 $1$,則輸出 $1$;
- 邏輯閘 $5$,若輸入 $2$ 或 $3$ 中至少有一個為 $1$,則輸出 $1$;以及
- 邏輯閘 $6$,若邏輯閘 $4$ 和邏輯閘 $5$ 的輸出皆為 $1$,則輸出 $1$。
可以驗證對於所有可能的輸入,該電路皆能給出正確答案。