Lỗi của tôi
Đề bài
Mô tả
Một mạch logic biến đổi đầu vào của nó qua các cổng logic để tạo ra đầu ra, và mạch không có vòng phản hồi. Đầu vào và đầu ra là các dãy giá trị logic có thứ tự, ở đây được biểu diễn bằng các số và . Các mạch được xét gồm cổng and (cho ra chỉ khi cả hai đầu vào đều bằng ), cổng or (cho ra khi một hoặc cả hai đầu vào bằng ), cổng xor (exclusive or, cho ra chỉ khi đúng một trong hai đầu vào bằng ) và cổng not (cho ra phần bù của đầu vào duy nhất của nó). Hai hình dưới đây minh họa hai mạch.

Hình 1: Mạch có 2 cổng

Hình 2: Mạch có 4 cổng
Không may là các cổng thật đôi khi bị hỏng. Dù cổng có thể hỏng theo nhiều cách khác nhau, bài toán này chỉ xét các cổng hỏng theo một trong ba cách: 1) luôn cho ra giá trị ngược với đầu ra đúng, 2) luôn cho ra , và 3) luôn cho ra . Trong các mạch của bài toán này, có nhiều nhất một cổng bị hỏng.
Hãy viết chương trình phân tích một mạch cùng một số lần quan sát đầu vào và đầu ra của nó để xem mạch hoạt động đúng hay sai. Nếu có ít nhất một bộ đầu vào cho ra đầu ra sai, chương trình còn phải cố gắng xác định cổng hỏng duy nhất và cách cổng đó bị hỏng. Điều này không phải lúc nào cũng làm được.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test, mỗi bộ test mô tả một mạch cùng các quan sát đầu vào và đầu ra. Mỗi bộ test gồm các phần sau, theo đúng thứ tự:
- Một dòng chứa ba số nguyên dương: số đầu vào , số cổng và số đầu ra của mạch.
- Mỗi cổng một dòng. Dòng đầu tiên mô tả cổng , nếu có nhiều cổng thì dòng tiếp theo mô tả cổng , và cứ thế. Mỗi dòng chứa loại cổng (
a= and,n= not,o= or,x= xor) và tên (các) đầu vào của cổng. Đầu vào của một cổng lấy từ các đầu vào của mạch (, viết lài1,i2, ...) hoặc từ đầu ra của một cổng khác (, viết làg1,g2, ...). - Một dòng chứa số hiệu của các cổng nối với đầu ra . Ví dụ, nếu có ba đầu ra, lấy từ , từ và từ , thì dòng này là: 5 1 4
- Một dòng chứa số nguyên là số lần quan sát hoạt động của mạch.
- Cuối cùng là dòng, mỗi dòng gồm giá trị ( hoặc ) là các giá trị đầu vào được quan sát, tiếp theo là giá trị là các giá trị đầu ra tương ứng được quan sát. Không có hai lần quan sát nào có cùng bộ giá trị đầu vào.
Các phần tử liên tiếp trên một dòng cách nhau đúng một dấu cách. Dữ liệu vào kết thúc bằng một dòng chứa ba số .
Dữ liệu ra
Với mỗi mạch, in ra số thứ tự của bộ test (bắt đầu từ ), tiếp theo là dấu hai chấm và một dấu cách, rồi đến kết quả phân tích mạch, là một trong các dòng sau (thay # bằng số hiệu cổng tương ứng):
No faults detected
Gate # is failing; output inverted
Gate # is failing; output stuck at 0
Gate # is failing; output stuck at 1
Unable to totally classify the failure
Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , , .
- Mạch không có vòng phản hồi (một cổng có thể lấy đầu vào từ cổng có số hiệu lớn hơn nó). Hai đầu vào của một cổng có thể là cùng một tín hiệu.
- .
- Mỗi file có không quá mạch và tổng các giá trị trong một file không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 o i1 i2 n g1 2 2 1 0 0 0 0 1 2 1 1 a i1 i2 1 1 1 0 1 2 1 1 a i1 i2 1 2 1 0 1 1 1 1 1 1 1 n i1 1 2 1 1 0 0 3 4 4 n g4 a i1 i2 o i2 i3 x i3 i1 2 3 4 1 4 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 |
Case 1: No faults detected Case 2: Unable to totally classify the failure Case 3: Gate 1 is failing; output stuck at 1 Case 4: Gate 1 is failing; output inverted Case 5: Gate 2 is failing; output stuck at 0 |
Mạch 1 là Hình 1, mạch 5 là Hình 2. Mạch 2: với đầu vào cổng and phải cho ra nhưng quan sát được ; cả "đảo đầu ra" lẫn "luôn ra " của cổng đều giải thích được nên không phân loại được. Mạch 3: quan sát thứ hai loại trừ "đảo đầu ra". |
| 1 1 1 n i1 1 1 1 0 2 3 1 o g2 i2 o i1 i2 n g1 1 4 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 |
Case 1: No faults detected Case 2: Gate 2 is failing; output inverted |
Mạch 1: quan sát khớp với mạch đúng, nên in "No faults detected" dù "cổng luôn ra " cũng khớp. Mạch 2: cổng lấy đầu vào từ cổng có số hiệu lớn hơn; chỉ có giả thiết "cổng đảo đầu ra" giải thích được cả bốn quan sát. |
Bình luận