QOJ.ac

QOJ

مجموع النقاط: 100 إخراج فقط

#18421. 三重電路

الإحصائيات

在為機器人實作電路時,你發現了一些異常。機器人可能會執行 $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

每一行分別代表新增一個 NOTORAND 邏輯閘。對於 NOTin_1 是該邏輯閘的輸入編號。對於 ORANDin_1in_2 是該邏輯閘的輸入編號。在第一行之後,第 $i$ 行所新增的邏輯閘編號為 $N-1 + i$。

邏輯閘總數不得超過 $1024$。換句話說,輸出檔案的總行數不得超過 $1025$。

子任務

  1. (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$。

可以驗證對於所有可能的輸入,該電路皆能給出正確答案。


أو قم برفع الملفات واحداً تلو الآخر:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.