trang chủ / đề bài / icpcwf09_b

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ố 1 và 0. Các mạch được xét gồm cổng and (cho ra 1 chỉ khi cả hai đầu vào đều bằng 1), cổng or (cho ra 1 khi một hoặc cả hai đầu vào bằng 1), cổng xor (exclusive or, cho ra 1 chỉ khi đúng một trong hai đầu vào bằng 1) 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 0, và 3) luôn cho ra 1. 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ự:

  1. Một dòng chứa ba số nguyên dương: số đầu vào N, số cổng G và số đầu ra U của mạch.
  2. Mỗi cổng một dòng. Dòng đầu tiên mô tả cổng g1, nếu có nhiều cổng thì dòng tiếp theo mô tả cổng g2, 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 (i1,i2,…, viết là i1, i2, ...) hoặc từ đầu ra của một cổng khác (g1,g2,…, viết là g1, g2, ...).
  3. Một dòng chứa số hiệu của các cổng nối với U đầu ra u1,u2,…. Ví dụ, nếu có ba đầu ra, u1 lấy từ g5, u2 từ g1 và u3 từ g4, thì dòng này là: 5 1 4
  4. Một dòng chứa số nguyên B là số lần quan sát hoạt động của mạch.
  5. Cuối cùng là B dòng, mỗi dòng gồm N giá trị (0 hoặc 1) là các giá trị đầu vào được quan sát, tiếp theo là U 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ố 0.

Dữ liệu ra

Với mỗi mạch, in ra số thứ tự của bộ test (bắt đầu từ 1), 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

  • N≤8, G≤19, U≤19.
  • 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.
  • 1≤B≤2N.
  • Mỗi file có không quá 1000 mạch và tổng các giá trị B trong một file không quá 20000.

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 1,0 cổng and phải cho ra 0 nhưng quan sát được 1; cả "đảo đầu ra" lẫn "luôn ra 1" của cổng 1 đề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 1 luôn ra 0" cũng khớp. Mạch 2: cổng 1 lấy đầu vào từ cổng 2 có số hiệu lớn hơn; chỉ có giả thiết "cổng 2 đảo đầu ra" giải thích được cả bốn quan sát.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0