解題區/解題區 - UVa

UVa 1080 - My Bad

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一個電路圖，有四種閘 AND, OR, XOR, NOT，接著給定閘的輸入端、輸出端，以及預期的輸入和輸出。

請問是否存在電路故障。若只有一個電路故障，輸出故障的情況，否則輸出無法判斷。

故障情況有反向、全為 1、全為 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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

Sample Output

1
2
3
4
5
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

Solution

如何橋接電路會比較難寫，這裡用 OO 的方式去撰寫，為了方便起見，設計輸入端口只會在 div ~ 512，剩餘在 0 ~ div。

接著窮舉損壞情況，對於每次窮舉，跑一次電路架構。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <stdio.h> 
#include <vector>
#include <assert.h>
#include <string.h>
#include <algorithm>
using namespace std;
class Circuit {
public:
    enum LOGIC {AND, OR, XOR, NOT, FV, F0, F1};
    struct Gate {
        LOGIC type;
        int p1, p2;
    } gates[1024];
    int inVal[512], outVal[512];
    int visited[512], sick[512];
    LOGIC sickType[512];
    int div = 256;
    void addGate(int id, LOGIC t, int in1, int in2 = 0) {
        gates[id].type = t;
        gates[id].p1 = in1, gates[id].p2 = in2;
    }
    int getInId(int x) {
        return div + x;
    }
    int getId(char s[]) {
        int x;
        sscanf(s+1, "%d", &x);
        return (s[0] == 'i') ? getInId(x) : x;
    }
    int getOutput(int id) {
        if (id > div)		return inVal[id - div];
        if (visited[id])	return outVal[id];
        visited[id] = 1;
        int &val = outVal[id];
        val = 0;
        if (gates[id].type == AND)
            val = (getOutput(gates[id].p1) & getOutput(gates[id].p2));
        if (gates[id].type == OR)
            val = (getOutput(gates[id].p1) | getOutput(gates[id].p2));
        if (gates[id].type == XOR)
            val = (getOutput(gates[id].p1) ^ getOutput(gates[id].p2));
        if (gates[id].type == NOT)
            val = !(getOutput(gates[id].p1));
        if (!sick[id])
            return val;
        if (sickType[id] == FV)
            return val = !val;
        else if (sickType[id] == F0)
            return val = 0;
        else
            return val = 1;
    }
    void clearSick()  {
        memset(sick, 0, sizeof(sick));
    }
    void clear() {
        memset(visited, 0, sizeof(visited));
    }
} g;
int N, G, U, B;
int outGate[128], IN[1024][128], OUT[1024][128];
char s[128], s1[128], s2[128];
int singleTest() {
    int ok = 1;
    for (int i = 0; i < B && ok; i++) {
        g.clear();
        for (int j = 1; j <= N; j++)
            g.inVal[j] = IN[i][j];
        for (int j = 1; j <= U; j++) {
            int v = g.getOutput(outGate[j]);
            ok &= v == OUT[i][j];
        }
    } 
    return ok;
}
void test() {
    g.clearSick();
    if (singleTest()) {
        puts("No faults detected");
        return;
    } 
    
    vector< pair<int, int> > err;
    for (int i = 1; i <= G; i++) {
        g.clearSick();
        g.sick[i] = 1, g.sickType[i] = Circuit::FV;
        if (singleTest())
            err.push_back(pair<int, int>(i, 0));
        g.sick[i] = 1, g.sickType[i] = Circuit::F0;
        if (singleTest())
            err.push_back(pair<int, int>(i, 1));	
        g.sick[i] = 1, g.sickType[i] = Circuit::F1;
        if (singleTest())
            err.push_back(pair<int, int>(i, 2));
        if (err.size() > 1)
            break;
    }
    if (err.size() > 1)
        puts("Unable to totally classify the failure");
    else {
        if (err[0].second == 0)
            printf("Gate %d is failing; output inverted\n", err[0].first);
        else if (err[0].second == 1)
            printf("Gate %d is failing; output stuck at 0\n", err[0].first);
        else if (err[0].second == 2)
            printf("Gate %d is failing; output stuck at 1\n", err[0].first);
    }
}
int main() {
    int cases = 0;
    while (scanf("%d %d %d", &N, &G, &U) == 3 && N) {
        for (int i = 1; i <= G; i++) {
            scanf("%s", s);
            if (s[0] == 'a') {
                scanf("%s %s", s1, s2);
                g.addGate(i, Circuit::AND, g.getId(s1), g.getId(s2));
            } else if (s[0] == 'o') {
                scanf("%s %s", s1, s2);
                g.addGate(i, Circuit::OR, g.getId(s1), g.getId(s2));
            } else if (s[0] == 'x') {
                scanf("%s %s", s1, s2);
                g.addGate(i, Circuit::XOR, g.getId(s1), g.getId(s2));
            } else {
                scanf("%s", s1);
                g.addGate(i, Circuit::NOT, g.getId(s1));
            }
        }
        
        for (int i = 1; i <= U; i++)
            scanf("%d", &outGate[i]);
        scanf("%d", &B);
        assert(B < 1024);
        for (int i = 0; i < B; i++) {
            for (int j = 1; j <= N; j++)
                scanf("%d", &IN[i][j]);
            for (int j = 1; j <= U; j++)
                scanf("%d", &OUT[i][j]);
        }
        
        printf("Case %d: ", ++cases);
        test();
    }
    return 0;
}
/*
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
*/